【题解】洛谷 P1470（codevs1052\2778）最长前缀 trie 树 —by litble

嗯嗯，这题啊，正解应该是 trie 树。
不过如果你够大佬，比如 xzy，就可以用 dfs 轻松 5msA 掉。
而本蒟蒻的 trie 树不仅代码量> 大佬 xzy，而且还用了 44ms。
真是失败。
好吧，思路是建立一棵 trie 树，然后对于字符串中的每一个字符，如果其前一个字符是某个单词的结尾，就深入这个 trie 树，并标记找到的所有单词结尾。注意最后一个字符也要特判。
代码：

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
char s[77],ss[200005];
int a[20005][28],tot,ans,ll;
bool f[200005],val[2005];
void tri(){
    int i,j,l=strlen(s),from=0,sum;
    for(i=0;i<l;i++){
        sum=s[i]-'A'+1;
        if(a[from][sum])from=a[from][sum];
        else {tot++;a[from][sum]=tot;from=tot;}
    }
    val[from]=1;
}
void init(int x){
    int i,j,from=0,sum;
    for(i=x;i<ll;i++){
        sum=ss[i]-'A'+1;
        if(a[from][sum])from=a[from][sum];
        else break;
        if(val[from])f[i]=1;
    }
}
int main()
{
    int i,j;
    while(1){scanf("%s",s);if(s[0]=='.')break;tri();}
    while(scanf("%s",s)!=EOF)strcat(ss,s);
    ll=strlen(ss);init(0);
    for(i=1;i<ll;i++)if(f[i-1]){init(i);ans=i;}
    if(f[ll-1])ans=ll;
    printf("%d",ans);
    return 0;
}