题目大意
给出一个模式串集合和一个被匹配串，问被匹配串的前多少位可以由模式串组成。
思路
AC自动机。先根据给出的模式串建树，然后与被匹配串进行匹配。
建立一个T_len[]数组，T_len[i]==x表示以T[i]为首匹配的单词的最大长度为x。求出T_len[]，就可以推导出答案，具体过程见solved()函数。
每次与模式串匹配成功时，都对T_len[]进行更新。当匹配结束，则T_len[]也更新完毕。
例如T[i]结尾的单词与长度为len的模式串匹配成功，则比较T_len[i-(len-1)]与len的大小，取两者中的较大值。其中i-(len-1)表示模式串在被匹配串中的匹配位置。
代码
/*
ID: lujunda1
LANG: C++
PROG: prefix
*/
#include
#include
#include
using namespace std;
#define T_SIZE 200000
#define P_SIZE 10
#define TOTAL_P 200
struct trie
//利用结构体来封装字典树的节点。
{
trie* next[26];
trie* fail;
bool tail;
//判断当前节点是否为某个单词的结尾。
int len;
//节点在字典树中的“深度”。
trie()
//构造函数。
{
for(int i=0;inext[s[i]-'A']==NULL)
{
p->next[s[i]-'A']=new trie;
p->next[s[i]-'A']->len=p->len+1;
}
p=p->next[s[i]-'A'];
}
p->tail=true;
}
void build_ac_automation(trie* root)
//利用广搜构建失败指针
{
int head=0,tail=0;
q[tail++]=root;
while(head!=tail)
{
trie* front=q[head++];
//front为队头元素
for(int i=0;inext[i]!=NULL)
//遍历队头元素的子节点
{
trie* p=front->fail;
while(p!=NULL)
//只有根节点的失败指针为NULL
{
if(p->next[i]!=NULL)
//顺着失败指针往回走，直至某个节点，其拥有一个字母为'A'+i的子节点。
{
front->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL)
//p==NULL说明顺着失败指针往回走的过程中没有找到合适的节点，所以将失败指针指向根节点。
front->next[i]->fail=root;
q[tail++]=front->next[i];
}
}
}
void ac_find(trie* root,char* T)
{
memset(T_len,0,sizeof(T_len));
trie* p=root;
for(int i=0,len=strlen(T);inext[T[i]-'A']==NULL&&p!=root)
//若当前节点的没有一个字符为T[i]的儿子且当前节点不是根节点
//通俗的讲，就是顺着失败指针往回走，直至找到合适的节点或根节点为止。
p=p->fail;
if(p->next[T[i]-'A']!=NULL)
//p->next[T[i]-'A']==NULL说明没找到合适的节点，p指针指在根节点上。
p=p->next[T[i]-'A'];
trie* temp=p;
while(temp!=root)
//顺着失败指针往回走，一直到根节点。
if(temp->tail)
{
if(T_len[i-(temp->len-1)]len)
T_len[i-(temp->len-1)]=temp->len;
break;
}
else
temp=temp->fail;
}
}
int solved()
{
int len=strlen(T),pos=-1;
//pos表示最长连续区间在T中的结尾位置。
for(int i=0;i<=pos+1&&ipos)
pos=T_len[i]+i-1;
return pos+1;
}
int main()
{
freopen("prefix.in","r",stdin);
freopen("prefix.out","w",stdout);
trie* root=new trie;
while(scanf("%s",P)&&strcmp(P,"."))
insert(root,P);
build_ac_automation(root);
T[0]='\0';
while(~scanf("%s",T+strlen(T)));
ac_find(root,T);
printf("%d\n",solved());
}