思路:建trie树,更新。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<algorithm> #include<cmath> #include<string> #include<vector> #include<queue> using namespace std; struct node { int a[27]; int s; }t[1111111]; char c[1111111]; int n,ans,num; void init() { memset(t[0].a,-1,sizeof(t[0].a)); t[0].s=0; num=0; } void trie(char *d) { int l=strlen(d); int p=0; ans=0; for(int i=0;i<l;i++) { if(t[p].a[d[i]-'a']==-1) { t[p].a[d[i]-'a']=++num; memset(t[num].a,-1,sizeof(t[num].a)); t[num].s=t[p].s+1; } int u=p; p=t[p].a[d[i]-'a']; t[p].s=min(t[p].s,t[u].s+1); } ans=t[p].s; } void update(char *d) { int p=0; int l=strlen(d); for(int i=0;i<l;i++) { int u=p; p=t[p].a[d[i]-'a']; t[p].s=min(t[p].s,l-i); t[p].s=min(t[p].s,t[u].s+1); } //cout<<d[l-1]<<" "<<t[p].s<<endl; } int main() { int T; scanf("%d",&T); while(T--) { init(); scanf("%d",&n); scanf("%s",c); trie(c); update(c); for(int i=0;i<n;i++) { scanf("%s",c); trie(c); printf("%d\n",ans); update(c); } } return 0; }