AC自动机+拓排--P3966 [TJOI2013]单词

problem

求各个模式串在文本串中出现了几次

solution

在AC自动机上先跑一边文本串，记录一下每个点都被经过的次数，那么单词被经过的次数就是他在fail树中的子树的权值和

可能博客写的比较简略 ，主要想记录一下这类题目的方法

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
int read(){
	int x = 1,a = 0;char ch = getchar();
	while (ch < ‘0‘||ch > ‘9‘){if (ch == ‘-‘) x = -1;ch = getchar();}
	while (ch >= ‘0‘&&ch <= ‘9‘){a = a*10+ch-‘0‘;ch = getchar();}
	return x*a;
}
const int maxn = 1e6+10;
int n;
int trie[maxn][30],cnt = 1;
char c[maxn];
int vis[maxn],fail[maxn],siz[maxn];
void build(char *a,int pos){
	int len = strlen(a),root = 1;
	for (int i = 0;i < len;i++){
		int nxt = a[i]-‘a‘;
		if (!trie[root][nxt]) trie[root][nxt] = ++cnt;
		root = trie[root][nxt];
		siz[root] ++;
	}
	vis[pos] = root;
}
int du[maxn];
void getfail(){
	queue<int> q;q.push(1);
	for (int i = 0;i < 26;i++) trie[0][i] = 1;
	while (!q.empty()){
		int root = q.front();q.pop();
		for (int i = 0;i < 26;i++){
			if (!trie[root][i]) trie[root][i] = trie[fail[root]][i];
			else{
				fail[trie[root][i]] = trie[fail[root]][i];
				du[trie[fail[root]][i]] ++;
				q.push(trie[root][i]);
			}
		}
	}
}
void toopo(){
	queue<int> q;
	for (int i = 1;i <= cnt;i++) if (du[i] == 0)  q.push(i);
	while (!q.empty()){
		int x = q.front();q.pop();
		int to = fail[x];
		siz[to] += siz[x],du[to]--;
		if (du[to] == 0) q.push(to);
	}
}
int main(){
	n = read();
	for (int i = 1;i <= n;i++){
		scanf ("%s",c);build(c,i);
	}
	getfail();
	toopo();
	for (int i = 1;i <= n;i++) printf("%d\n",siz[vis[i]]);
	return 0;
}

AC自动机+拓排--P3966 [TJOI2013]单词

原文：https://www.cnblogs.com/little-uu/p/14051581.html