题目描述
求最长公共前缀
另一种方法
用 trie树 求解后缀问题
样例
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int son[N][59],cut[N],idx;
int n,len;
void init(){
memset(son,0,sizeof(son));
memset(cut,0,sizeof(cut));
idx=0;
len=0;
}
void insert(string a){
int p=0;
for(int i=a.size()-1;i>=0;i--){
int u=a[i]-'A';
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
cut[p]++;
}
}
int query(string a){
int p=0;
for(int i=a.size()-1;i>=0;i--){
int u=a[i]-'A';
p=son[p][u];
if(cut[p]==n) len++;
else break;
}
return len;
}
int main(){
while(cin>>n,n){
init();
string a,b;
cin>>b;insert(b);
for(int i=1;i<n;i++){
cin>>a;insert(a);
if(a.size()<b.size()) b=a;
}
cout<<b.substr(b.size()-query(b))<<endl;
}
return 0;
}