zoj 1825 Compound Words

ZOJ Problem Set - 1825 Compound Words

---

Time Limit: 5 Seconds      Memory Limit: 32768 KB

---

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 Submit    Status

---

// 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 ; }

 

//用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 ; }

转载于:https://www.cnblogs.com/forever4444/archive/2009/05/21/1485964.html

相关资源：数据结构—成绩单生成器