UVa10391 Compound Words

想了半天, 总是绕不开那个该死的O(N²).

看了看题解, 发现直接枚举每个单词的子串就ok了...

对啊..毕竟最长的单词

Pneumonoultramicroscopicsilicovolcanoconiosis(肺尘病)

也不过45个字母嘛...

所以啊, 想不出来的时候,可以考虑从相反的方向思考

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <vector>
 5 #include <set>
 6 #include <algorithm>
 7 using namespace std;
 8 const int MAXN = 120000 + 20;
 9 
10 string str[MAXN];
11 set<string> S;
12 vector<string> ans;
13 
14 int main()
15 {
16     ios::sync_with_stdio(false);
17     int cnt = 0;
18     while(cin>>str[++cnt]) S.insert(str[cnt]);
19 
20     string tmp1, tmp2;
21     for(int i = 1; i <= cnt; i++)
22         for(int j = 1; j < (int) str[i].size() - 1; j++)
23         {
24             tmp1 = str[i].substr(0, j),
25             tmp2 = str[i].substr(j, str[i].size() - j);
26 
27             if(S.find(tmp1) != S.end() && S.find(tmp2) != S.end()){
28                 ans.push_back(str[i]);
29                 break;
30             }
31         }
32 
33     sort(ans.begin(), ans.end());
34     for(int i = 0; i < (int) ans.size(); i++)
35         cout<<ans[i]<<endl;
36     return 0;
37 }