最复杂的一道字符串
字典的迭代器
substr的应用
思路（抄）：
用哈希表存储已知的每个字符串的等级。
对于需要判断的字符串s：
首先判断是否已知， 若为真直接输出即可
枚举每个已知等级的字符串， 判断其是否为s的前缀，若为前缀则判断s除去这部分前缀后的部分是否已知等级， 若都已知， 则拼接
此过程中记录拼接的次数， 若不为一则定为D级。
时间复杂度O ( N M ) O(NM)O(NM)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m, n, i = 0;
cin >> m >> n;
string a, b, s, res;
map<string, string> level;
for (i; i < m; i++)
{
cin >> a >> b;
level[a] = b;
}
for (i = 0; i < n; i++)
{
cin >> s;
if (level.count(s))
cout << level[s] << endl;
else
{
int cnt = 0;
for (auto &p : level)
{
if (p.first.size() < s.size() && s.substr(0, p.first.size()) == p.first && level.count(s.substr(p.first.size())))
{
cnt++;
cout << level[s.substr(0, p.first.size())] << level[s.substr(p.first.size())] << endl;
// res = level[s.substr(0, p.first.size())] + level[s.substr(p.first.size())];
}
}
if (cnt != 1)
{
cout << "D" << endl;
}
}
}
return 0;
}
改：
for (auto &p : level)
{
if (p.first.size() < s.size() && s.substr(0, p.first.size()) == p.first && level.count(s.substr(p.first.size())))
{
cnt++;
res=level[s.substr(0, p.first.size())] + level[s.substr(p.first.size())];
}
}
if (cnt != 1)
{
res="D";
}cout<<res<<endl;
}
}
return 0;
}
结果单独存储避免重复输出