ZOJ Problem Set - 1825
You are to find all the two-word compound words in a dictionary. A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 120,000 words.
Output
Your output should contain all the compound words, one per line, in alphabetical order.
Sample Input
a
alien
born
less
lien
never
nevertheless
new
newborn
the
zebra
Sample Output
alien
newborn
Source: University of Waterloo Local Contest 1996.09.28
//1846335 2009-04-28 15:41:20 Accepted 1825 C++ 270 1240 Wpl
#include <iostream>
#include <string>
#include <set>
using namespace std;
set<string>S;
set<string>::iterator p;
int main()
{
string str,str1,str2;
S.clear();
int len,i;
while(cin>>str)
{
S.insert(str);
}
for(p=S.begin();p!=S.end();p++)
{
str=*p;
len=str.length();
for(i=1;i<len;i++)
{
str1=str.substr(0,i);
str2=str.substr(i,len-i);
if(S.find(str1)!=S.end()&&S.find(str2)!=S.end())
{
cout<<str<<endl;
break;
}
}
}
return 0;
}
#include <iostream>
#include <string>
#include <set>
using namespace std;
set<string>S;
set<string>::iterator p;
int main()
{
string str,str1,str2;
S.clear();
int len,i;
while(cin>>str)
{
S.insert(str);
}
for(p=S.begin();p!=S.end();p++)
{
str=*p;
len=str.length();
for(i=1;i<len;i++)
{
str1=str.substr(0,i);
str2=str.substr(i,len-i);
if(S.find(str1)!=S.end()&&S.find(str2)!=S.end())
{
cout<<str<<endl;
break;
}
}
}
return 0;
}
//用map
//1846363 2009-04-28 16:02:33 Wrong Answer 1825 C++ 410 3616 Wpl
//1846374 2009-04-28 16:11:40 Accepted 1825 C++ 240 1372 Wpl
#include <iostream>
#include <map>
#include <string>
using namespace std;
map<string,int>M;
map<string,int>::iterator p;
int main()
{
string str,str1,str2;
int len,i;
M.clear();
while(cin>>str)
M[str]=1;
for(p=M.begin();p!=M.end();p++)
{
str=p->first;
len=str.length();
for(i=1;i<len;i++)
{
str1=str.substr(0,i);
str2=str.substr(i,len-i);
// if(M[str1]==1&&M[str2]==1) //找数不用这样找的,因为这样会把那个数放进M里
if(M.find(str1) != M.end() && M.find(str2) != M.end())
{
cout<<str<<endl;
break;
}
}
}
return 0;
}
//1846374 2009-04-28 16:11:40 Accepted 1825 C++ 240 1372 Wpl
#include <iostream>
#include <map>
#include <string>
using namespace std;
map<string,int>M;
map<string,int>::iterator p;
int main()
{
string str,str1,str2;
int len,i;
M.clear();
while(cin>>str)
M[str]=1;
for(p=M.begin();p!=M.end();p++)
{
str=p->first;
len=str.length();
for(i=1;i<len;i++)
{
str1=str.substr(0,i);
str2=str.substr(i,len-i);
// if(M[str1]==1&&M[str2]==1) //找数不用这样找的,因为这样会把那个数放进M里
if(M.find(str1) != M.end() && M.find(str2) != M.end())
{
cout<<str<<endl;
break;
}
}
}
return 0;
}