P2292 [HNOI2004] L 语言

给出字典（个数为 \(n\)）和文章（个数为 \(m\) ），求文章最大匹配前缀。\(n\leq 20,m\leq 50\) , \(|s|\leq 20, |t|\leq 2\times 10^6\)

首先想到用AC自动机，在每个字串结尾标记串的长度，即 \(bj[p]=slen\) 。构造一个 \(ans\) 数组， \(ans[i]=1\) 表示 \(ans[i]\) 之前都可以被理解。初值 \(ans[0]=1\) ，若在 \(trie\) 上匹配成功， \(ans[i]=ans[i] | ans[i-bj[p]]\) 。最后从尾到头扫描，第一次 \(ans[i]=1\) 时即为答案。

期望得分：85pt

#include<bits/stdc++.h>
using namespace std;


int n,m;
int trie[30][405],cnt,bj[405],fa[405],num[405],nxt[405],ans[2000005];
char s[2000005];
queue <int> q;

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%s",s);
		int slen=strlen(s);
		int p=0;
		for(int j=0;j<slen;++j)
		{
			if(trie[s[j]-'a'][p])
				p=trie[s[j]-'a'][p];
			else
			{
				cnt++;
				num[cnt]=s[j]-'a';
				fa[cnt]=p;
				trie[s[j]-'a'][p]=cnt;
				p=cnt;
			}
		}
		bj[p]=slen;
	}
	q.push(0);
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		for(int i=0;i<26;++i)
		{
			if(trie[i][p])
				q.push(trie[i][p]);
		}
		if(fa[p]==0)
			continue;
		int j=nxt[fa[p]];
		while(j && trie[num[p]][j]==0)
			j=nxt[j];
		if(trie[num[p]][j])
			j=trie[num[p]][j];
		nxt[p]=j;
	}
	for(int i=1;i<=m;++i)
	{
		scanf("%s",s+1);
		int slen=strlen(s+1);
		int p=0;
		ans[0]=1;
		for(int j=1;j<=slen;++j)
		{
			while(p && trie[s[j]-'a'][p]==0)
				p=nxt[p];
			if(trie[s[j]-'a'][p])
				p=trie[s[j]-'a'][p];
			int t=p;
			while(t)
			{
				ans[j]=ans[j] | ans[j-bj[t]];
				t=nxt[t];
			}
		}
		for(int j=slen;j>=0;--j)
		{
			if(ans[j])
			{
				printf("%d\n",j);
				break;
			}
		}
		memset(ans,0,sizeof(ans));
	}
	return 0;
}

再考虑正解，加强后AC自动机要跑 \(2\times10^6\times50=10^8\) 次，如果跳跃的次数太多，不可能不超时。

考虑到子串长度 \(<=20\) ，可以尝试用状压来做（事实上最后使用的是bitset），具体做法：将 \(bj\) 数组记为跳跃之后可以达到的长度集，在 \(bfs\) 求 \(fail\) 指针时，每当找到一个点 \(p\) 的 \(nxt\) 指针，立刻让 \(bj[p]=bj[p] | bj[nxt[p]]\) ，这样在求 \(fail\) 指针的同时也求出了完整的 \(bj\) 集。

定义一个 \(anss\) ，记为在最近20个字符中 \(ans=1\) 的字符集（ \(ans\) 定义与上同），那么在长串匹配时如果 \(anss\&bj[p]!=0\) ,则表示现在匹配的 \(ans=1\) ，加入 \(anss\) 集，同时删除 \(anss\) 中超过20的部分，是常数级运算。

在真正实现时，用 \(bitset\) 的左移来模拟 \(anss\) 中删除的操作。100pt！

#include<bits/stdc++.h>
using namespace std;


int n,m;
int trie[30][405],cnt,fa[405],num[405],nxt[405],lst;
char s[2000005];
bitset <25> anss;
bitset <25> bj[405];

queue <int> q;

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%s",s);
		int slen=strlen(s);
		int p=0;
		for(int j=0;j<slen;++j)
		{
			if(trie[s[j]-'a'][p])
				p=trie[s[j]-'a'][p];
			else
			{
				cnt++;
				num[cnt]=s[j]-'a';
				fa[cnt]=p;
				trie[s[j]-'a'][p]=cnt;
				p=cnt;
			}
		}
		bj[p][slen]=1;
	}
	q.push(0);
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		for(int i=0;i<26;++i)
		{
			if(trie[i][p])
				q.push(trie[i][p]);
		}
		if(fa[p]==0)
			continue;
		int j=nxt[fa[p]];
		while(j && trie[num[p]][j]==0)
			j=nxt[j];
		if(trie[num[p]][j])
			j=trie[num[p]][j];
		nxt[p]=j;
		bj[p]=(bj[p] | bj[j]);
	}
	for(int i=1;i<=m;++i)
	{
		scanf("%s",s+1);
		int slen=strlen(s+1);
		int p=0;
		anss[0]=1;
		lst=0;
		int j;
		for(j=1;j<=slen;++j)
		{
			anss<<=1;
			while(p && trie[s[j]-'a'][p]==0)
				p=nxt[p];
			if(trie[s[j]-'a'][p])
				p=trie[s[j]-'a'][p];
			if((anss&bj[p])!=0)
			{
				anss[0]=1;
				lst=j;
			}
			if(j-lst>20)
				break;
		}
		printf("%d\n",lst);
		anss.reset();
	}
	return 0;
}