本文主要是介绍USACO Section 2.3 Longest Prefix，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你一大堆小字符串 和 一个大字符串 求 使用小字符串能拼出的大字符串的前缀最长是多少
思路：
由于数据不大 所以可以尝试扫描大字符串 每到一个位置用小字符串拼一下看看能拼多长 拼的最远距离就是答案
我用trie树来存小字符串集合 扫描大字符串时 如果该位置是可以向后延伸的（即之前能拼到这个位置）
那么我用一个标记在trie树上爬 每次发现一个小字符串结束标志 就表示对应大字符串的位置是可延伸的
这样做下标记并更新答案
注意：
这题的坑是这句话 —— “the input file contains a sequence S (length 1..200,000) expressed as one or more lines, none of which exceeds 76 letters in length” 他的大字符串是分几行输入的… 千万不要只用一个%s去读入
代码：
/*
ID: housera1
PROG: prefix
LANG: C++
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;struct node
{int flag;int next[28];
}trie[20100];
char tmp[210],str[200010]={0};
int vis[200010];
int n=1,ans=0;void make_tree()
{int i=0,len=strlen(tmp),now=0;for(;i<len;i++){if(trie[now].next[tmp[i]-'A']!=-1) now=trie[now].next[tmp[i]-'A'];else{trie[now].next[tmp[i]-'A']=n;trie[n].flag=0;for(int j=0;j<26;j++) trie[n].next[j]=-1;now=n;n++;}}trie[now].flag=1;
}void run(int start,int L)
{int i,j;for(i=start,j=0;;i++){if(trie[j].flag){vis[i]=1;ans=max(ans,i);}if(trie[j].next[str[i]-'A']!=-1) j=trie[j].next[str[i]-'A'];else break;}
}int main(){int Debug=0;if(!Debug){freopen("prefix.in","r",stdin);freopen("prefix.out","w",stdout);}int i,len;trie[0].flag=0;for(i=0;i<26;i++) trie[0].next[i]=-1;while(scanf("%s",tmp)){if(strcmp(tmp,".")==0) break;make_tree();}while(~scanf("%s",tmp)){strcat(str,tmp);}len=strlen(str);for(i=0,vis[0]=1;i<len;i++){if(vis[i]) run(i,len);}printf("%d\n",ans);return 0;
}
这篇关于USACO Section 2.3 Longest Prefix的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
