695
uva 10391 - Compound Words
判斷一個單詞是不是組合詞，題目中說是不同的單詞，但是如果加不同判斷就會WA……所以直接無視就好了
一共最多有120000的單詞，這種題有兩個思路，1是合成詞，2是拆分詞。
合成詞的複雜度是n^2果斷超時
拆分詞是n*m（m為平均長度），因為m未知，所以抱著試一試的想法，用map水了一下，就過了，120ms，可見m的長度並不大
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <map>
#define INF 1E9
using namespace std;
map<string,bool> hash;
string s[150000];
int main()
{
int i,j;
int cnt=0;
hash.clear();
while(cin>>s[cnt])
{
hash[s[cnt]]=1;
cnt++;
}
string a,b;
for(i=0;i<cnt;i++)
for(j=0;j<s[i].size()-1;j++)
{
a=s[i].substr(0,j+1);
if(!hash[a])continue;
b=s[i].substr(j+1);
if(!hash[b])continue;
cout<<s[i]<<endl;
break;
}
return 0;
}
最後更新：2017-04-02 22:15:57