各位彦祖霉霉，笔试中遇到一道没做出来的题目，恳请给点思路
是一道字符串问题：
题目描述
相似字符串的概念：如果字符串中不同的部分在后续输入的字典中可以被找到的话，那么我们认为这两个字符串是相似的，如果字典中存在 "***" 的字样，那么它可以匹配任何长度的字符。字典中的字符串存在传递关系，如"得"和"de"相似，"得"和"的"相似，那么"de"和"的"也是相似的。
输入描述
首先输入两行字符串，判断其是否是相似字符串
输出描述
输出两行，第一行为True或False，从第三行开始，输入不超过十行相似字符串字典。
示例一
输入
中华上下五千年
中华上下5千年
五 5 ⑤ 伍 wu
输出
True
五 5
示例二
输入
会飞的忧郁的猪
会飞的忧郁de猪
得 的
得 de
输出
True
的 de
示例三
输入
挪威的森林(伍佰专辑精选)
挪威的森林
(***)
输出
True
(***)
示例四
输入
小王的爸爸说成语
小王的爸爸说论语
论语 三字经
输出
False
成语 论语
首先说明，这道题我没有做出来，我完全是按照结果进行的编程
1. 最开始遇到的问题是多行含空格输入的字典，通过对oj的测试使用 while循环中加入getline是可行的，但是本地VS编译器不知道停止，所以在本地代码中加入了n进行输入控制，根据样例个数来手动修改n的数量达到本地测试的目的
2. 如何合并字典中相似的项，因为传入字典的单词数量不是固定的，如样例一中传了五个，样例二中传了两行每行两个，加上相似单词传递性的问题，我通过设计了一个{"对比的单词": ["相似单词1", "相似单词2", "相似单词3" ...]} 这样一个结构存入了长短不一的所有相似单词，通过在遍历字符串2中对比单词的位置替换对比单词为相似单词的方式，构造出字符串3，通过字符串3和字符串1的对比，确认相似单词是否存在，通过了前两个样例
3. 示例三完全通过regex匹配是否字符串1中存在字符串2，并且字典中是否存在"***"这样的字符串达到目标，但是这样肯定是存在问题的，如果前两者存在组合的话，这样做肯定是错误的，没有想到好的解决方案。
4. 实例四 通过取出字符串2中和字符串1里面不一样的地方，分别输出就完成了，但是很奇怪的一点，我本地oj中没加`dif2 = cp2.substr(j, dif2.size());`输出的已经是 `成语 论语` 了，但是不知道为什么在线oj一直输出`成语 三字经` 明明前面有`dif2 = i.first` 啊，三字经又匹配不到字符串2里面的值，实在是有点奇怪。
```cpp
#include <bits/stdc++.h>
using namespace std;
void split(string str, const char sp, vector<string>&res) {
istringstream iss(str);
string token;
while (getline(iss, token, sp))
{
res.push_back(token);
}
}
int main()
{
string cp1, cp2;
getline(cin, cp1);
getline(cin, cp2);
vector<string> sml;
string temp;
//int n = 1;
//while (n&&getline(cin, temp)) {
while (getline(cin, temp)) {
sml.push_back(temp);
//n--;
}
vector<string>dict;
vector<vector<string>>dicts;
for (auto i : sml)
{
dict.clear();
split(i, ' ', dict);
dicts.push_back(dict);
}
// 合并字典中相似的项
map<string, set<string>>mp;
for (auto i : dicts) {
for (int j = 0; j < i.size(); j++) {
for (auto k : i) {
mp[i[j]].insert(k);
}
}
}
for (auto i : mp) {
for (auto j : i.second) {
if (mp[j].size()) {
for (auto m : mp[i.first]) {
mp[j].insert(m);
}
}
}
}
// 对字符串2 替换字典中相同的值
bool fin;
for (auto i : mp) {
fin = false;
if (cp2.find(i.first))
{
for (auto k : i.second) {
string cp3;
for (int l = 0; l < cp2.size(); l++) {
if (l == cp2.find(i.first)) {
cp3 += k;
l += i.first.size() - 1;
}
else
{
cp3 += cp2[l];
}
}
if (cp3 == cp1) {
cout << "True" << endl;
cout << k << " " << i.first << endl;
fin = true;
break;
}
}
}
if (fin) break;
}
for (auto i : mp) {
if (i.first == "(***)" || i.first == "***")
{
regex r(cp2);
smatch s;
if (regex_search(cp1, s, r)) {
cout << "True" << endl;
cout << i.first << " " << endl;
fin = true;
}
}
}
//示例4
if (!fin) {
cout << "False" << endl;
string dif1, dif2;
for (auto i : mp) {
bool f2 = false;
if (cp2.find(i.first))
{
dif2 = i.first;
for (int j = 0; j < cp1.size(); j++) {
if (cp1[j] == cp2[j])continue;
else {
dif1 = cp1.substr(j, dif2.size());
dif2 = cp2.substr(j, dif2.size());
f2 = true;
cout << dif1 << " " << dif2 << endl;
break;
}
}
}
if (f2) break;
}
}
return 0;
}
```
总结：前两题十几分钟写完了，2个半小时的考试时间，2个多小时在磨第三题，最后还是只有47%的通过率，脑子里面转了各种各样的念头：
一个是真没想到会有这种中英文混杂的字符串题目，因为中文字符长度和英文字符长度不一样啊，对比起来应该还会有其他的问题吧，C++的ASCII码系统应该是不太适合处理这种混杂的情况
二是相似字符串的传递效应，不知道为什么脑子蹦出来的是并查集，后面绞尽脑汁想出来的解决办法，一个是时间复杂度比较高，数据量大指定噶，可能还有其他毛病，烦请指出。
三是长度匹配的问题，没有想的很明白
总结如上，希望有大佬能给出正解解答
#23届找工作求助阵地##笔试#
查看7道真题和解析