洛谷 P5231 [JSOI2012]玄武密码

原题链接

Solution

\(AC\)自动机

一道小清新 \(AC\) 自动机题目

我们对于所有的 \(t\) 建出 \(trie\) 图及 \(fail\) 指针，把母串 \(s\) 放到上面跑，假设 \(s\) 的前缀跳 \(fail\) 指针跳到节点 \(x\)，根据 \(fail\) 指针的定义，一定有一个短串 \(t\) 的前缀在母串 \(s\) 上，所以我们把 节点 \(x\) 打上标记。

再把 \(m\) 个询问放回到 \(trie\) 树上跑（相当于是把 \(trie\) 树搜了一遍），遇到有标记的点就更新答案。

还要把 \(E，S，W，N\) 转化为 1，2，3，4 以降低空间复杂度。

具体看代码吧

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 1e7 + 10;
const int M = 1e5 + 10;
int n, m;
char t[N],s[M][110];
int trie[N][5], tot, fail[N];
bool vis[N];

int calc(char c){	//转化
	if(c == 'E') return 0;
	if(c == 'S') return 1;
	if(c == 'W') return 2;
	if(c == 'N') return 3;
	return -1;
}
//--------------------------------------------------AC自动机模板不解释
void insert(char s[]){
	int len = strlen(s);
	int now = 0;
	for(int i = 0; i < len; i++){
		int x = calc(s[i]);
		if(!trie[now][x]) trie[now][x] = ++tot;
		now = trie[now][x];
	}
}

void build(){
	queue <int> q;
	for(int i = 0; i < 4; i++)
		if(trie[0][i])
			q.push(trie[0][i]);
	while(!q.empty()){
		int now = q.front();
		q.pop();
		for(int i = 0; i < 4; i++){
			if(trie[now][i]){
				fail[trie[now][i]] = trie[fail[now]][i];
				q.push(trie[now][i]);
			}else trie[now][i] = trie[fail[now]][i];
		}
	}
}

void query(char s[]){
	int now = 0;
	for(int i = 0; i < n; i++){
		now = trie[now][calc(s[i])];
		int res = now;
		while(res && !vis[res])
			vis[res] = 1, res = fail[res];
	}
}

int solve(char s[]){
	int len = strlen(s);
	int now = 0, ans = -1;
	for(int i = 0; i < len; i++){
		now = trie[now][calc(s[i])];
		if(vis[now]) ans = i;
	}
	return ans;
}

int main(){
	scanf("%d%d%s", &n, &m, t);
	for(int i = 1; i <= m; i++){
		scanf("%s", s[i]);
		insert(s[i]);
	}
	build();
	query(t);
	for(int i = 1; i <= m; i++)
		printf("%d\n", solve(s[i]) + 1);		//查找长度要+1
	return 0;
}

End