分成两段来判断,也是一道字典树的裸题
#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; typedef struct Trie { bool v; Trie *next[26]; }Trie; char s[50100][50],str1[100],str2[100]; Trie *root; void createTrie(char *str) { Trie *p=root,*q; int len=strlen(str); for(int i=0;i<len;i++) { int id=str[i]-'a'; if(p->next[id]==NULL) { q=new Trie; for(int j=0;j<26;j++) q->next[j]=NULL; q->v=false; p->next[id]=q; p=q; } else p=p->next[id]; } p->v=true; } bool findTrie(string str) { int len=str.length(); Trie *p=root; for(int i=0;i<len;i++) { int id=str[i]-'a'; if(p==NULL||p->next[id]==NULL) return false; p=p->next[id]; } return p->v; } void del(Trie *root) { for(int i=0;i<26;i++) { if(root->next[i]!=NULL) del(root->next[i]); } free(root); } int main() { // freopen("input.txt","r",stdin); int i,cnt=0; char str[50]; root=new Trie; for(i=0;i<26;i++) root->next[i]=NULL; root->v=false; while(gets(str)) { strcpy(s[cnt++],str); createTrie(str); } int k,t; for(i=0;i<cnt;i++) { for(int j=1;j<strlen(s[i]);j++) { for(k=0;k<j;k++) str1[k]=s[i][k]; str1[k]=NULL; for(k=0,t=j;t<strlen(s[i]);t++,k++) str2[k]=s[i][t]; str2[k]=NULL; if(findTrie(str1)&&findTrie(str2)) { cout<<s[i]<<endl; break; } } } del(root); return 0; }