https://vjudge.net/problem/UVA-10391
给一堆单词，其中有些单词可以由其他两个单词（可以相同）复合得到，输出符合这个性质的所有单词。\(n\le 120000\)
把所有单词存进set，然后枚举两个单词，加起来在set里面查找。时间复杂度\(O(n^2)\) \(\mathbb{TLE}\)
放弃了:(
反过来把一个单词拆成两个单词。可以用string的 c_str() 或 data() 函数，得到只读的C风格字符串，时间复杂度\(O(n\log n)\)
c++11以前c_str()返回的指针是以‘\0‘结尾的，而data()并不要求这一点。
https://en.cppreference.com/w/cpp/string/basic_string/c_str
https://en.cppreference.com/w/cpp/string/basic_string/data
所以还是用c_str()吧……
AC代码
#include <bits/stdc++.h>
#define REP(i,x,y) for(register int i=x; i<(y); i++)
#define REPE(i,x,y) for(register int i=x; i<=(y); i++)
#ifdef LOCAL
#define DBG(x,...) printf(x, ##__VA_ARGS__)
#else
#define DBG(x,...) (void)(0)
#endif
using namespace std;
set<string> st;
set<string> ans;
int main()
{
char s[1007];
while(~scanf("%s", s)) st.insert(s);
for(set<string>::iterator it=st.begin(); it!=st.end(); it++) {
string now = *it;
char sa[1007], sb[1007];
strcpy(sa,now.c_str());
strcpy(sb,now.c_str());
for(int i=now.size()-1; i>0; i--) {
sa[i]=0;
if(st.count(sa) && st.count(&sb[i])) {
ans.insert(now);
}
}
}
for(set<string>::iterator it=ans.begin(); it!=ans.end(); it++) {
cout << *it << endl;
}
return 0;
}
其实还可以加个字符串数组，减小常数……
原文：https://www.cnblogs.com/sahdsg/p/10367285.html