本文共 1189 字，大约阅读时间需要 3 分钟。
题意：给出n个单词（1<=n<=1000），求出每个单词的非公共前缀，如果没有，则输出自己。
#include #include #include #include #include #include #include #include #include using namespace std;struct Node{ int c; int next[26];} node[20005];int cnt;int newnode(){ ++cnt; node[cnt].c=0; for(int i=0; i<26; i++) node[cnt].next[i]=-1; return cnt;}char s[1006][25];int len[1006];void insert(int rt,int tt,int now){ if(now>len[tt])return; int p=s[tt][now]-'a'; if(node[rt].next[p]==-1) { int l=newnode(); node[rt].next[p]=l; node[l].c+=1; insert(l,tt,now+1); } else { int l=node[rt].next[p]; node[l].c+=1; insert(l,tt,now+1); }}void print(int rt,int tt,int now){ if(now>len[tt])return; printf("%c",s[tt][now]); if(node[rt].c==1)return; int p=s[tt][now+1]-'a'; print(node[rt].next[p],tt,now+1);}int main(){ int k=0; cnt=0; node[0].c=0; for(int i=0;i<26;i++) node[0].next[i]=-1; while(~scanf("%s",s[++k]+1)) { len[k]=strlen(s[k]+1); insert(0,k,1); } for(int i=1;i<=k;++i) { printf("%s ",s[i]+1); int p=s[i][1]-'a'; print(node[0].next[p],i,1); printf("\n"); } return 0;}
转载于:https://www.cnblogs.com/d-e-v-i-l/p/4928141.html