小结：ac自动机

复杂度：

查找O(n)，维护O(n)

概要：

应用了kmp的自匹配思想，在trie建图时维护一个fali指针，指向上一个匹配的点，这点是用bfs做到。匹配串的时候同样没匹配到就和kmp一样返回。

应用：单串匹配多模板，维护多模板里边的信息。

技巧及注意：

插入和trie一样，然后是bfs。

在bfs的过程中，注意以根开头的不需要匹配fail，即ch[0][i]不需要匹配他们的fail，即为空。

然后在查找的时候当找到一个时我们要遍历这个节点的整个fail树，然后取出信息后记得将信息清空。

一定要注意！节点数是不超过n个串的总长度！！！一定要切记！！！

注意！！bfs的时候一定要维护信息！！！！

例题：

【BZOJ】1030: [JSOI2007]文本生成器（递推+ac自动机）（将自动机的节点作为转移的状态然后递推）

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

using namespace std;

const int N=10000000, Type=26;

int T[N][Type], w[N], fail[N], cnt, q[N], front, tail, ans;

char str[1000000], st[1000000];

inline void ins(char s[]) {

	int len=strlen(s), now=0;

	rep(i, len) {

		int t=s[i]-'a';

		if(!T[now][t]) T[now][t]=++cnt;

		now=T[now][t];

	}

	++w[now];

}

void bfs() {

	int now=0;

	q[tail++]=0;

	while(tail!=front) {

		now=q[front++]; if(front==N) front=0;

		rep(i, 26) if(T[now][i]) {

			q[tail++]=T[now][i]; if(tail==N) tail=0;

			if(now==0) continue;

			int p=fail[now];

			while(p && !T[p][i]) p=fail[p];

			fail[T[now][i]]=T[p][i];

		}

	}

}

void ac(char s[]) {

	int len=strlen(s), now=0;

	rep(i, len) {

		int t=s[i]-'a';

		while(now && !T[now][t]) now=fail[now];

		now=T[now][t];

		t=now;

		while(t) {

			ans+=w[t];

			w[t]=0;

			t=fail[t];

		}

	}

}

int main() {

	scanf("%s", str);

	int n=getint();

	while(n--) {

		scanf("%s", st);

		ins(st);

	}

	bfs();

	ac(str);

	print(ans);

	return 0;

}

没错，就是AC自动机！（可惜不像金坷垃那样～）

不多说，放上模板，不难理解的。

#include <cstdio>

#include <cstring>

#include <queue>

#define for1(i,a,n) for(i=a;i<=n;++i)

#define for2(i,a,n) for(i=a;i<n;++i)

#define for3(i,a,n) for(i=n;i>=a;--i)

#define for4(i,a,n) for(i=n;i>a;--i)

#define CC(i,a) memset(i, a, sizeof(i))

using namespace std;

const int N=10000000, Type=26;

char a[N], b[N];

int ch[N][Type], fail[N], w[N], ans, cnt=1;

queue<int> q;

void ins(char* s) {

	int u=0, v, i, len=strlen(s);

	for2(i, 0, len) {

		v=s[i]-'a';

		if(!ch[u][v]) ch[u][v]=cnt++;

		u=ch[u][v];

	}

	w[u]++;

}

void bfs() {

	fail[0]=0;

	q.push(0);

	int u, p, i;

	while(!q.empty()) {

		u=q.front(); q.pop();

		for2(i, 0, Type) if(ch[u][i]) {

			q.push(ch[u][i]); //先插入，后判断

			if(!u) continue; //不要在这里错了。。

			p=fail[u];

			while(p && !ch[p][i]) p=fail[p];

			fail[ch[u][i]]=ch[p][i];

		}

	}

}

void ac(char* s) {

	int i, u=0, v, len=strlen(s), t;

	for2(i, 0, len) {

		v=s[i]-'a';

		while(u && !ch[u][v]) u=fail[u];

		u=ch[u][v];

		t=u;

		while(t) {

			ans+=w[t];

			w[t]=0;

			t=fail[t];

		}

	}

}

void init() {

	CC(fail, 0);

	CC(ch, 0);

	CC(w, 0);

}

int main() {

	init();

	scanf("%s", a);

	int n, i;

	scanf("%d", &n);

	for1(i, 1, n) {

		scanf("%s", b);

		ins(b);

	}

	bfs();

	ac(a);

	printf("%d\n", ans);

	return 0;

}

注意一些细节即可

巴特西

小结：ac自动机

复杂度：

概要：

技巧及注意：

最新文章

热门文章