洛谷 P3808 【模板】AC自动机（简单版）（AC自动机优化板子）

题中有一个坑点，就是模式串可以相同，并且全部计数。

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

const int N=maxn;

char str[maxn];

struct Dfa {

	int trie[N][26],cnt;

	int e[N];

	int fail[N];

	char ch;

	void init(char c) {

		memset(trie,0,sizeof(trie));

		memset(e,0,sizeof(e));

		memset(fail,0,sizeof(fail));

		cnt=0;

		ch=c;

	}

	void insert(char * s) {

		int p=0;

		for (int i=0;s[i];i++) {

			int to=s[i]-ch;

			if (trie[p][to]==0) {

				trie[p][to]=++cnt;

			}

			p=trie[p][to];

		}

		e[p]++;

	}

	void build() {

		queue<int> q;

		for (int i=0;i<26;i++) {

			if (trie[0][i]) {

				q.push(trie[0][i]);

			}

		}

		while (!q.empty()) {

			int root=q.front();

			q.pop();

			for (int i=0;i<26;i++) {

				if (trie[root][i]) {

					fail[trie[root][i]]=trie[fail[root]][i];

					q.push(trie[root][i]);

				}

				else {

					trie[root][i]=trie[fail[root]][i];

				}

			}

		}

	}

	long long query(char * s) {

		long long ans=0;

		int p=0;

		for (int i=0;s[i];i++) {

			p=trie[p][s[i]-ch];//第一层的空节点k trie[0][k]=0

			for (int j=p;j&&~e[j];j=fail[j]) {

				ans+=e[j];

				e[j]=-1;

			}

		}

		return ans;

	}

}dfa;

int main()

{

	int n;

	dfa.init('a');

	scanf("%d",&n);

	while (n--) {

		scanf("%s",str);

		dfa.insert(str);

	}

	dfa.build();

	scanf("%s",str);

	printf("%lld\n",dfa.query(str));

	return 0;

}

巴特西

洛谷 P3808 【模板】AC自动机（简单版）（AC自动机优化板子）

最新文章

热门文章

巴特西

洛谷 P3808 【模板】AC自动机（简单版） （AC自动机优化板子）

最新文章

热门文章

洛谷 P3808 【模板】AC自动机（简单版）（AC自动机优化板子）