关于AC自动机
  • 板块学术版
  • 楼主Anonymely
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/1/15 14:05
  • 上次更新2023/10/24 04:08:57
查看原帖
关于AC自动机
550957
Anonymely楼主2023/1/15 14:05
#include<bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define eps 0.00000001
#define ll long long
#define orz puts("-1")
#define pf(x) printf("%s",x);
#define pii pair<int,int>
#define pb push_back
#define mk make_pair
#define newline puts("")
#define newspace putchar(' ')
#define lowbit(x) (x&(-x))
#define md(l,r) ((l+r)>>1)
#define lson(p) (p<<1)
#define rson(p) ((p<<1)|1)
#define fi first
#define se second
#define inf 2147483647
#define mod
#define N 1000010

namespace fastIO{
	template<typename T> void read(T &x){
		x=0;
		char ch=getchar();T fl=1;
		while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();};
		while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();};
		x=x*fl;
	}
	template<typename T, typename ...T1> void read(T &x, T1 &...x1){
		read(x);
		read(x1...);
	}
	template<typename T> void write(T x){
		if(x<0){
			x=-x;putchar('-');
		}
		if(x/10)write(x/10);
		putchar(x%10+'0');
	}
	template<typename T> void writer(T x){
		write(x);
		putchar(' ');
	}
	template<typename T> void writen(T x){
		write(x);
		putchar('\n');
	}
}

using namespace fastIO;

int n;
int t[N][26], tot, lst[N][26];
int val[N * 26], fail[N * 26], vis[N * 26];
string s;

void init() {
	memset(t, -1, sizeof(t));
}

void insert(string s) {
	int rt = 0;
	for (int i = 0; i < s.length(); i++) {
		if (t[rt][s[i] - 'a'] == -1) t[rt][s[i] - 'a'] = ++tot;
		rt = t[rt][s[i] - 'a'];
	}
	val[rt]++;
}

void build() {
	fail[0] = -1;
	queue<int> q;
	for (int i = 0; i < 26; i++) {
		if (t[0][i] != -1) q.push(t[0][i]), fail[t[0][i]] = 0;
		else lst[0][i] = 0;
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < 26; i++) {
			if (t[x][i] != -1) {
				int rt = fail[x];
				while (rt != -1) {
					if (t[rt][i]) {
						fail[t[x][i]] = t[rt][i];
						break;
					}
					rt = fail[rt];
				}
				if (rt == -1) fail[t[x][i]] = 0;	
				q.push(t[x][i]);		
			} else {
				int rt = fail[x];
				while (rt != -1) {
					if (t[rt][i]) {
						lst[x][i] = t[rt][i];
						break;
					}
					rt = fail[rt];
				}
				if (rt == -1) lst[x][i] = 0;				
			}
		}
	}
}

int query(string s) {
	int rt = 0, res = 0;
	for (int i = 0; i < s.length(); i++) {
		if (t[rt][s[i] - 'a'] != -1) rt = t[rt][s[i] - 'a'];
		else rt = lst[rt][s[i] - 'a'];
		for (int j = rt; j != 0 && vis[j] != -1; j = fail[j]) res += val[j], vis[j] = -1;
	}
	return res;
}

void file() {
	freopen("qwq.in", "r", stdin);
	//freopen("qwq.out", "w", stdout);
}

signed main() {
//	file(); 
	cin >> n;
	init();
	for (int i = 1; i <= n; i++) {
		cin >> s;
		insert(s); 
	}
	build();
	cin >> s;
	write(query(s));
	return 0;
}

rt,想写一个 n2n^2 的AC自动机来帮忙理解,但是板子题第二个点总是Wa

2023/1/15 14:05
加载中...