题目大意

给出一个模式串集合和一个被匹配串，问被匹配串的前多少位可以由模式串组成。

思路

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<iostream>
#include<stdio.h>
#include<cstring>
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;i<26;i++)
			next[i]=NULL;
		fail=NULL;
		tail=false;
		len=0;
	}
};

char T[T_SIZE+1];
char P[P_SIZE+1];
trie* q[TOTAL_P*P_SIZE];
int T_len[T_SIZE+1];
//T_len用于本题，记录连续区间。
//例：“T_len[i]==x”表示以T[i]为首匹配的单词的最大长度为x。 

void insert(trie* root,char* s)
//将字符串s所表示的单词插入到字典树中。
{
	trie* p=root;
	for(int i=0;s[i]!='\0';i++)
	{
		if(p->next[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;i<26;i++)
			if(front->next[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);i<len;i++)
	{
		while(p->next[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)]<temp->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&&i<len;i++)
		if(T_len[i]+i-1>pos)
			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());
}