1050 String Subtraction (20) 字符串处理

Given two strings $S_1$ and $S_2$ $S=S_1-S_2$ is defined to be the remaining string after taking all the characters in $S_2$ from $S_1$. Your task is simply to calculate $S_1-S_2$ for any given strings. However, it might not be that simple to do it fast.

Input Specification

Each input file contains one test case. Each case consists of two lines which gives $S_1$ and $S_2$​​ , respectively. The string lengths of both strings are no more than $10^4$​ . It is guaranteed that all the characters are visible ASCII codes and white space, and a new line character signals the end of a string.

Output Specification

For each test case, print $S_1-S_2$ in one line.

Sample Input

They are students.
aeiou

Sample Output

Thy r stdnts.

思路1

1. 设置一个哈希表数组表示字符串 b 中出现了哪些字符，遍历字符串 a 将未出现的字符进行输出，否则跳过即可。
2. 用 flag[256] 数组变量标记 str2 出现过的字符为 true，输出str1 的时候根据 flag[str1[i]] 是否为 true ,如果是 true 就不输出。

代码1

#include <iostream>
using namespace std;
const int maxn = 256;
bool flag[maxn];
int main()
{
    string a, b;
    getline(cin, a);
    getline(cin, b);
    for (int i = 0; i < b.length(); i++)
        flag[b[i]] = true;
    for (int i = 0; i < a.length(); i++)
        if (!flag[a[i]])
            cout << a[i];
    cout << endl;
    return 0;
}

思路2

1. 使用 unordered_set 作为哈希表实现(内部无序)
2. insert 插入函数 将元素加入哈希表
3. count 查询函数，如果该元素在哈希表中出现过则返回1，否则返回0
4. 将出现过的未出现的字符进行拼接即可

代码2

#include <iostream>
#include <unordered_set>
using namespace std;

string s1, s2;

int main()
{
    getline(cin, s1);
    getline(cin, s2);
    unordered_set<char> hash;  // 定义哈希表
    for (auto c : s2) hash.insert(c);  // 将s2中的字符插入哈希表
    string res;
    for (auto c : s1)
        if (!hash.count(c))
            res += c;
    cout << res << endl;
    return 0;
}