洛谷P2808 AC自动机

AC自动机 $<mpadded width="0px"> ̸ </mpadded> =$ 自动AK机!!!

题目背景

省略…

题目描述

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

输入输出格式

输入格式：

第一行一个n，表示模式串个数；

下面n行每行一个模式串；

下面一行一个文本串。

输出格式：

一个数表示答案

输入输出样例

输入样例#1：

2
a
aa
aa

输出样例#1：

说明

subtask1[50pts]:∑length(模式串)<=10^{6,length(文本串)<=10}6,n=1；

subtask2[50pts]:∑length(模式串)<=10^{6,length(文本串)<=10}6；

code

#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <algorithm>
#include <queue>
using namespace std ;
struct dy{
	int fail ;
	int vis[30] ;
	int end ;
}ac[1100000] ;
int cnt = 0 ;
void build(string s) ;
void get_fail() ;
int ac_query(string s) ;
int n ;
int read() ; 
int main() {
	int n ;
	string s ;
	n = read() ;
	for(int i = 1 ; i <= n ; i ++) {
		cin >> s ;
		build(s) ;
	}
	ac[0].fail = 0 ;
	get_fail() ;
	cin >> s ;
	cout << ac_query(s) << endl ;
	return 0;
} 
int ac_query(string s) {
	int l = s.size() ;
	int now = 0 , ans = 0 ;
	for(int i = 0 ; i < l ; i ++) {
		now = ac[now].vis[s[i]-'a'] ;
		for(int t = now;t&&ac[t].end!=-1;t = ac[t].fail) {
			ans += ac[t].end ;
			ac[t].end = -1 ;
		}
	}
	return ans ;
}
void get_fail() {
	queue<int>q ;
	for(int i = 0 ; i < 26 ; i ++) {
		if(ac[0].vis[i] != 0) {
			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] != 0) {
				ac[ac[u].vis[i]].fail = ac[ac[u].fail].vis[i] ;
				q.push(ac[u].vis[i]) ;
			}else ac[u].vis[i] = ac[ac[u].fail].vis[i] ;
		}
	}
}
void build(string s) {
	int l = s.size() ;
	int now = 0 ;
	for(int i = 0 ; i < l ; i ++ ) {
		if(ac[now].vis[s[i]-'a'] == 0) 
		ac[now].vis[s[i]-'a'] = ++cnt ;
		now = ac[now].vis[s[i]-'a'] ;
	}
	ac[now].end += 1 ;
}
int read() {
	int x = 0 ;int f = 1 ;char s = getchar() ;
	while(s>'9'||s<'0') {if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0') {x=x*10+(s-'0');s=getchar();}
	return x*f ;
}

只是用来存档的于是就没有加注释

其实是L_Y_T的懒癌啦QwQ

完结撒金坷垃!!