AC自动机模板求助P3808
  • 板块灌水区
  • 楼主Buried_Dream
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/12/27 11:00
  • 上次更新2023/10/28 13:30:37
查看原帖
AC自动机模板求助P3808
396974
Buried_Dream楼主2021/12/27 11:00

50分求助:

/*
work by: TLE_Automation
Time: O(TLE)
knowledge:
*/
#include<bits/stdc++.h>
#define TLE std
#define int long long
#define Min(x, y)  (x > y ? y : x);
#define Max(x, y)  (x > y ? x : y);
#define orz cout << "szt lps fjh AK IOI";
using namespace TLE;

const int maxn = 3e6;
const int MAXN = 3e3;
const double down = 0.996;
const double limit = 1e-10;

inline int read() {
	int s = 0, w = 1;
	char ch = getchar();
	while (!isdigit(ch)) {if(ch == '-') {w = -1;}ch = getchar();}
	while (isdigit(ch)) {s = (s << 1) + (s << 3) + (ch ^ 48);ch = getchar();}
	return s * w;
}

inline void print(int x) {
	if (x < 0 ) putchar('-'), x = -x;
	if (x > 9 ) print(x / 10);
	putchar(x % 10 + '0');
}

const int MAX = 26;
int cnt = 0;

struct node {
	int fail, vis[MAX], end;
}AC[maxn];

void build(string s) {
	int now = 0;
	int len = s.length();
	for(int i = 0; i < len; i++) {
		if(!AC[now].vis[s[i] - 'a']) {
			AC[now].vis[s[i] - 'a'] = ++cnt;
		}
		now = AC[now].vis[s[i] - 'a'];
	}
	AC[now].end ++;
	return;
}

void Fail() {
	queue <int> q;
	for(int i = 0; i < 26; i++) {
		if(AC[0].vis[i]) {AC[AC[0].vis[i]].fail = 0;q.push(AC[0].vis[i]);}
	}
	while(!q.empty()) {
		int u = q.front();q.pop();
		for(int i = 0; i < 26; i++) {
			if(AC[u].vis[i]) {
				AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
			}else {
				AC[u].vis[i] = AC[AC[u].fail].vis[i];
			}
		}
	}return;
}
	
int AC_query(string s) {
	int len = s.length();
	int now = 0, res = 0;
	for(int i = 0; i < len; i++) {
		now = AC[i].vis[s[i] - 'a'];
		for(int j = now; j != 0 && AC[j].end != -1; j = AC[j].fail) {
				res += AC[j].end;
				AC[j].end = -1;
		}
	}return res;
}


signed main() {
//	freopen("P3808_2.in", "r", stdin);
//	freopen("ans.out", "w", stdout);
	int n = read();
	string s;
	for(int i = 1; i <= n; i++) {
		cin >> s;
		build(s);
	}
	AC[0].fail = 0;
	Fail();
	cin >> s;
	cout << AC_query(s) << endl;
	return 0;
}
2021/12/27 11:00
加载中...