/*
Date: 2012/10/27
題目鏈接地址：http://acm.hdu.edu.cn/showproblem.php?pid=1247
思路：把字典中的每個字符串拆成0->j 和 j->n 兩個子串，再分別查找這兩個子串
????? 在不在字典中，若在則滿足題意
*/

方法1：字典樹

#include<iostream> #include<string> using namespace std; #define maxn 50001 string s[maxn]; struct Trie {int n;Trie *next[26];Trie(){n = 0;memset(next,0,sizeof(next));} }; void Insert(Trie *root,string s) {Trie *p = root;for(int i = 0; i < s.size(); i++){int j = s[i] - 'a';if(p->next[j] == NULL) p->next[j] = new Trie();p = p->next[j];}p->n++; } bool Find(Trie *root,string s) {Trie *p = root;for(int i = 0; i < s.size(); i++){int j = s[i] - 'a';if(p->next[j] == NULL) return false;p = p->next[j];}if(p->n > 0) return true;return false; } int main() {//freopen("1001.txt","r",stdin);int n = 0;Trie *root = new Trie();while(cin >> s[n])Insert(root,s[n++]);for(int i = 0; i < n; i++)for(int j = 1; j < s[i].size()- 1; j++){string s1(s[i],0,j); //表示把s[i]中從下標0開始連續的j個字符賦給s1
string s2(s[i],j,s[i].size()-j);if(Find(root,s1) && Find(root,s2)){cout << s[i] << endl;break;}}return 0; }

?

?

方法2：stl中的map

?

#include<iostream> #include<map> #include<string> using namespace std; string s[50001]; int main() {//freopen("1001.txt","r",stdin);int n = 0;map<string,int> m;while(cin >> s[n])m[s[n++]] = 1;for(int i = 0; i < n; i++)for(int j = 1; j < s[i].size() - 1; j++){string s1(s[i],0,j); ////表示把s[i]中從下標0開始連續的j個字符串賦給s1??
string s2(s[i],j,s[i].size()-j);if(m[s1] == 1 && m[s2] == 1){cout << s[i] << endl;break;}}return 0; }

?

轉載于:https://www.cnblogs.com/sorryhao/archive/2012/10/27/2743039.html

總結

以上是生活随笔為你收集整理的HDU 1247(Hat’s Words )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。