526互联

uva10391 复合词 Compound Words

发布时间 2023-12-10 22:55:17作者: 黑屿白

原题链接 复合词 Compound Words - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题我的第一想法是二重循环遍历所有组合，但结合120000的数据量知晓此方法肯定超时。

那么解法二：先用map存储所有的单词，再遍历所有的单词（假如为S），对S进行分解得到Sa和Sb，然后判断Sa和Sb在不在map中（第二次遍历时的次数必定小于120000）。

此处我使用了STL中的count函数和string中的substr函数

主要代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    set<string> set1;
    string s;
    while (cin>>s) set1.insert(s);
    for (set<string>::iterator i=set1.begin();i!=set1.end();i++){
        int l=(*i).size();
        for (int j=1;j<l;j++){
            if (set1.count((*i).substr(0,j))&&set1.count((*i).substr(j))){
                cout<<(*i)<<endl;
                break;
            }
        }
    }
    return 0;
}