UVA 10391 Compound Words -

题目地址：http://vjudge.net/problem/UVA-10391

一开始是想枚举任意两个单词

/*
for i 1 nfor j i+1 nif find(str[i]+str[j])!=NULL then save
O(n*n*logn)
*/

然而单词长度是很小的，所以不如直接拆分单词，找组成这两个单词的单词是否存在

 
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b)  for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int maxn=120000+5;
string str[maxn];
int n=0;
bool Search(string x){int L=0,R=n-1;while(L<=R){int mid=(L+R)>>1;if(str[mid]==x) return true;else if(str[mid]<x) L=mid+1;else R=mid-1;}return false;
}
int main(int argc, char const *argv[])
{string temp; while(cin>>temp) str[n++]=temp;REP(i,0,n-1) REP(j,1,str[i].length()-1) if(Search(str[i].substr(0,j))&&Search(str[i].substr(j))) {cout<<str[i]<<endl;break;}return 0;
}