BZOJ 4327 [JSOI2012]玄武密码 (AC自动机)

题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=4327

题解:

做法挺显然，建出AC自动机之后在上面跑，标记所有走过的点，然后再进行递推，如果\(fail[x]\)被标记则\(x\)被标记，然后每一个关键点往上找即可

有一个常数优化的技巧: 如果枚举每个\(x\)再vis[fail[x]]|=vis[x]的话好像还需要按深度排序，不如直接每到一个点直接不停地跳fail一路标记，直到遇到已标记点为止

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

const int N = 1e5;

const int LEN = 100;

const int M = 1e7;

const int SIZ = 1e7;

const int S = 4;

char b[N+3][LEN+3];

char a[M+3];

int len[N+3];

int son[SIZ+3][S+3];

int fail[SIZ+3];

int id[SIZ+3];

bool vis[SIZ+3];

int que[SIZ+3];

int ans[N+3];

int n,m,siz;

int decode(char x)

{

	if(x=='E') return 1;

	else if(x=='S') return 2;

	else if(x=='W') return 3;

	else if(x=='N') return 4;

}

void insertstr(int sid)

{

	int u = 0;

	for(int i=1; i<=len[sid]; i++)

	{

		if(son[u][b[sid][i]]==0) {siz++; son[u][b[sid][i]] = siz;}

		u = son[u][b[sid][i]];

	}

	id[u] = sid;

}

void buildACA()

{

	int head = 1,tail = 0;

	for(int i=1; i<=S; i++)

	{

		if(son[0][i]) {tail++; que[tail] = son[0][i];} fail[son[0][i]] = 0;

	}

	while(head<=tail)

	{

		int u = que[head]; head++;

		for(int i=1; i<=S; i++)

		{

			if(son[u][i]) {fail[son[u][i]] = son[fail[u]][i]; tail++; que[tail] = son[u][i];}

			else {son[u][i] = son[fail[u]][i];}

		}

	}

}

int main()

{

	scanf("%d%d",&m,&n);

	scanf("%s",a+1); for(int i=1; i<=m; i++) a[i] = decode(a[i]);

	for(int i=1; i<=n; i++)

	{

		scanf("%s",b[i]+1); len[i] = strlen(b[i]+1);

		for(int j=1; j<=len[i]; j++) b[i][j] = decode(b[i][j]);

		insertstr(i);

	}

	buildACA();

	int u = 0; vis[0] = true;

	for(int i=1; i<=m; i++)

	{

		vis[u] = true;

		u = son[u][a[i]];

		for(int j=u; vis[j]==false; j=fail[j]) {vis[j] = true;}

	}

	for(int i=1; i<=n; i++)

	{

		u = 0;

		for(int j=1; j<=len[i]; j++)

		{

			u = son[u][b[i][j]];

			if(!vis[u]) {break;}

			ans[i]++;

		}

	}

	for(int i=1; i<=n; i++) printf("%d\n",ans[i]);

	return 0;

}

巴特西

BZOJ 4327 [JSOI2012]玄武密码 (AC自动机)

代码

最新文章

热门文章