题目链接：USACO-Longest Prefix
考虑到所有给定串的元素长度<=10，所以可以用dp来搞。dp[i]表示从1~i是否是一个符合条件的前缀。 然后转移就行。 可以用Trie树来加速某个子串是否出现在元素中。
/* ID: xdujlx1 PROG: prefix LANG: C++ */ #include<bits/stdc++.h> using namespace std; bool dp[200007]; string s; struct Trie { int root,next[2007][26],T,end[2007]; int newnode() { memset(next[T],0,sizeof(next[T])); return T++; } void init() { T=0; root=newnode(); memset(end,0,sizeof(end)); } void insert(const string & s) { int n=s.length(); int now=root; for(int i=0;i<n;i++) { if(!next[now][s[i]-'A']) next[now][s[i]-'A']=newnode(); now=next[now][s[i]-'A']; } end[now]=true; } bool count(int l,int r) { int now=root; for(int i=l;i<=r;i++) { if(!next[now][s[i]-'A']) return false; now=next[now][s[i]-'A']; } return end[now]; } }; Trie t; void ioinit() { freopen("prefix.in","r",stdin); freopen("prefix.out","w",stdout); } int main() { ioinit(); t.init(); dp[0]=true; string ss; while(1) { cin>>ss; if(ss==".") break; t.insert(ss); } s.push_back('1'); while(cin>>ss) s.insert(s.length(),ss); int ans=0; int n=s.length()-1; for(int i=1;i<=n;i++) { for(int j=i-1;j>=0&&i-j<=10;j--) { if(!dp[j]) continue; if(t.count(j+1,i)) { dp[i]=true; ans=max(ans,i); break; } } } cout<<ans<<endl; return 0; }