2021.11.10 P5231 [JSOI2012]玄武密码（AC自动机）

2021.11.10 P5231 [JSOI2012]玄武密码（AC自动机）

https://www.luogu.com.cn/problem/P5231

题意：

给出字符串S和若干T，求S与每个T的最长公共前缀。

分析：

建AC自动机之后对于S每个出现的位置i以及fail[t[u][i]]打上标记，继续寻找i=fail[i]直到i>0，然后对每个T单独寻找，从0到strlen(T)-1如果有标记，更新ans。

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int N=1e7+10;

int n,m;

char t[100010][110],s[N];

namespace trie{

	int t[N][4],vis[N],fail[N],tot;

	queue<int>q;

	int id(char ch){

		if(ch=='N')return 1;

		if(ch=='S')return 2;

		if(ch=='W')return 3;

		if(ch=='E')return 0;

		//上北下南，左西右东

	}

	void insert(char *s){

		int len=strlen(s),u=0;

		for(int i=0;i<len;i++){

			int v=id(s[i]);

			if(!t[u][v])t[u][v]=++tot;

			u=t[u][v];

		}

	}

	void build(){

		for(int i=0;i<4;i++)if(t[0][i])q.push(t[0][i]);

		while(!q.empty()){

			int u=q.front();q.pop();

			for(int i=0;i<4;i++){

				if(t[u][i])fail[t[u][i]]=t[fail[u]][i],q.push(t[u][i]);

				else t[u][i]=t[fail[u]][i];

			}

		}

	}

	void flag(char *s){

		int u=0;

		int len=strlen(s);

		for(int i=0;i<len;i++){

			int v=id(s[i]);

			u=t[u][v];

			for(int j=u;j&&!vis[j];j=fail[j])vis[j]=1;

		}

	}

	int find(char *s){

		int u=0,len=strlen(s);

		int ans=-1;

		for(int i=0;i<len;i++){

			int v=id(s[i]);

			u=t[u][v];

			if(vis[u])ans=i;

		}

		return ans+1;

	}

}

int main(){

	cin>>n>>m;

	scanf("%s",s);

	for(int i=1;i<=m;i++)scanf("%s",t[i]),trie::insert(t[i]);

	trie::build();

	trie::flag(s);

	for(int i=1;i<=m;i++)cout<<trie::find(t[i])<<endl;

	return 0;

}

2021.11.10 P5231 [JSOI2012]玄武密码（AC自动机）的相关教程结束。