【GESP】C++三级练习 luogu-B3654 [语言月赛202208] 影子字符串

GESP C++三级练习，字符串和一维数组相关，难度★★☆☆☆。

luogu-B3654 [语言月赛202208] 影子字符串

题目要求

题目描述

给出多个字符串（数目未知），每行一个。

其中有可能会有重复的字符串，而我们认为在这些字符串中，较靠后出现的都是靠前出现的字符串的“影子”。

例如，
PLAIN
abc
def
abc
abc
abc
我们在第 $1,3,4,5$ 行都出现了字符串 abc，那么 $3,4,5$ 行的字符串会被称为“影子字符串”。

现在要求把所有的非影子字符串都按照行号从小到大依次拼接为一个长串并输出。

输入格式

多个字符串，每行一个，含义见题目描述。

注意：输入结尾以字符串 0 结束（即一行里仅有一个 0）。

输出格式

共一行，表示所有非影子字符串按照行号从小到大依次拼接成的一个长串。

输入输出样例 #1

输入 #1

PLAIN

cc
b
a
cc
0

输出 #1

PLAIN

ccba

说明/提示

对于 $20\%$ 的数据，无重复字符串。

对于 $100\%$ 的数据， $1\leq 字符串的数量\leq 500$ ，字符串总长度不超过 $50000$ ，字符集为全部的小写字母、数字、 . 、! 和 &。

也就是说，每个字符串中只包含小写字母、数字、. 、! 和 &，不包含空格等特殊符号。

题目分析

解题思路

本题的解题思路如下：

问题分析：
- 输入多个字符串，每行一个，以"0"结束
- 需要识别并去除"影子字符串"（重复出现的字符串）
- 按照原始行号顺序拼接所有非影子字符串
解题方法：
- 核心思路：
  - 使用数组存储已出现的字符串
  - 对每个新输入的字符串，检查是否为影子字符串
  - 只保留首次出现的字符串（非影子字符串）
- 实现方式：
  - 方法一：先存储后输出，使用数组保存所有非影子字符串
  - 方法二：边读入边输出，遇到非影子字符串直接输出
实现要点：
- 字符串数量范围：1 ≤ 字符串数量 ≤ 500
- 字符串只包含小写字母、数字、'.'、'!'和'&'
- 总字符串长度不超过50000
- 需要按原始输入顺序处理字符串

复杂度分析：

时间复杂度： $O(n^2)$ ，其中n为输入字符串数量，需要对每个字符串在已有字符串中查重
空间复杂度： $O(n)$ ，需要存储所有非影子字符串

示例代码

方法一，使用数组存储非影子字符串，最后统一输出

CPP

#include <iostream>
#include <string>

int main() {
    // 当前读入的字符串
    std::string cur_str;
    // 存储非影子字符串的数组
    std::string str_ary[500];
    // 最终结果字符串
    std::string result_str;
    // 当前数组索引
    int cur_idx = 0;

    // 循环读入字符串直到遇到"0"
    while (true) {
        std::cin >> cur_str;
        // 遇到"0"时退出循环
        if (cur_str == "0") {
            break;
        }

        // 标记当前字符串是否已存在
        bool is_exist = false;
        // 遍历已存储的字符串检查是否重复
        for (int i = 0; i < cur_idx; i++) {
            if (str_ary[i] == cur_str) {
                is_exist = true;
                break;
                ;
            }
        }

        // 如果是非影子字符串则存储
        if (!is_exist) {
            str_ary[cur_idx] = cur_str;
            cur_idx++;
        }
    }

    // 按顺序输出所有非影子字符串
    for (int i = 0; i < cur_idx; i++) {
        std::cout << str_ary[i];
    }
    return 0;
}

方法二，边读入边输出非影子字符串

CPP

#include <iostream>
#include <string>

int main() {
    // 定义字符串数组用于存储输入的字符串
    std::string str_ary[501];
    // 当前数组索引，初始化为-1
    int cur_idx = -1;
    while (true) {
        // 移动到下一个位置
        cur_idx++;
        // 读入当前字符串
        std::cin >> str_ary[cur_idx];
        // 如果读入"0"，表示输入结束
        if (str_ary[cur_idx] == "0") {
            break;
        }
        // 标记当前字符串是否为影子字符串
        bool is_exist = false;
        // 遍历之前的所有字符串，检查是否存在重复
        for (int i = 0; i < cur_idx; i++) {
            if (str_ary[i] == str_ary[cur_idx]) {
                is_exist = true;
                break;
            }
        }
        // 如果不是影子字符串，直接输出
        if (!is_exist) {
            std::cout << str_ary[cur_idx];
        }
    }
    return 0;
}

C++ 算法考级专栏