「學習筆記」AC 自動機

點擊查看目錄

目錄
「學習筆記」AC 自動機
演算法
問題
思路
代碼
例題
Keywords Search
玄武密碼
單詞
病毒
最短母串
文本生成器
背單詞
密碼
禁忌

前置：「學習筆記」字串基礎：Hash，KMP與Trie，

好像對例題的講解越來越抽象了？

演算法

問題

求 \(n\) 個單詞在一個長度為 \(m\) 的文章里出現過多少個，

思路

很多文章都說這玩意是 Trie 樹 + KMP，我覺得確實可以這樣理解但是不完全一樣，

KMP 有兩種理解方式：求 Border 或失配指標，AC 自動機用的是「失配指標」這個理解方式，

KMP 的失配指標指向的是一個最長的與后綴一樣的前綴，這樣仍然可以繼續匹配，而且使需要重新匹配的地方盡量短，

AC 自動機 \(\text{fail}\) 指標指向的則是一個存在于這個 Trie 樹中的最長的與真后綴相同的字串，

~~依舊是~~拿 OI-wiki 的圖舉個例子：

比如單詞 she，它的真后綴有 he，e 和（\(\leftarrow\) 這個真后綴是空的），其中 he 和存在于 Trie 樹中，則讓 \(9\) 號節點的 \(\text{fail}\) 指標指向最長的 he 的末尾節點 \(2\) 號節點，

再如單詞 her，它的真后綴有 er，r 和，但是只有存在于 Trie 樹中，則讓 \(3\) 號節點的 \(\text{fail}\) 指標指向根節點 \(0\)，

那么怎么找到 \(\text{fail}\) 指標呢？

我們設當前節點 \(p\) 代表的字符是 \(c\)，則 \(p\) 的 \(\text{fail}\) 指標應指向 \(p\) 的父親的 \(\text{fail}\) 指標的代表 \(c\) 的兒子，

例如上圖中，\(9\) 代表的字符是 e，\(9\) 的父親是 \(8\)，\(8\) 的 \(\text{fail}\) 指標指向 \(1\)，\(1\) 的代表 e 的兒子是 \(2\)，因此 \(9\) 的 \(\text{fail}\) 指標指向 \(2\) 號節點，

很好理解吧！~~xrlong said：沒看出來，~~

但是有個問題，比如圖中的六號節點應指向哪里？\(6\) 的父親 \(5\) 的 \(\text{fail}\) 指標 \(10\) 的代表 s 的兒子不存在，但是很明顯應指向 \(7\) 啊！

那就跳到 \(10\) 號節點的 \(\text{fail}\) 指標 \(0\)，找 \(0\) 的代表 s 的兒子 \(7\)，但是每次跳很多 \(\text{fail}\) 指標效率太低了，怎么辦？

那就魔改一下這棵樹！如果 \(p\) 不存在代表 \(c\) 的兒子，那就讓 \(p\) 代表 \(c\) 的兒子指向 \(p\) 的 \(\text{fail}\) 指標的代表 \(c\) 的兒子，

就像下面這幅圖：

生物書食物鏈

最后再次放一下 OI-wiki 上的完整動圖：

食物鏈的形成程序

藍色結點：BFS 遍歷到的結點 \(u\)，
藍色的邊：當前結點下，AC 自動機修改字典樹結構連出的邊，
黑色的邊：AC 自動機修改字典樹結構連出的邊，
紅色的邊：當前結點求出的 \(\text{fail}\) 指標，
黃色的邊：\(\text{fail}\) 指標，
灰色的邊：字典樹的邊，

代碼

namespace ACAUTOMATON {
	class ACAutomaton {
	private:
		ll cnt = 0, nxt[N][26], fail[N], end[N];
	public:
		inline void Clear () {
			cnt = 0;
			memset (nxt, 0, sizeof (nxt));
			memset (end, 0, sizeof (end));
			memset (fail, 0, sizeof (fail));
			return;
		}
		inline void Insert (char* s) {
			ll p = 0, len = strlen (s + 1);
			_for (i, 1, len) {
				ll c = s[i] - 'a';
				if (!nxt[p][c]) nxt[p][c] = ++cnt;
				p = nxt[p][c];
			}
			++end[p];
			return;
		}
		inline void Build () {
			std::queue <ll> q;
			_for (i, 0, 25) if (nxt[0][i]) fail[nxt[0][i]] = 0, q.push (nxt[0][i]);
			while (!q.empty ()) {
				ll u = q.front (); q.pop ();
				_for (i, 0, 25) {
					if (nxt[u][i]) fail[nxt[u][i]] = nxt[fail[u]][i], q.push (nxt[u][i]);
					else nxt[u][i] = nxt[fail[u]][i];
				}
			}
			return;
		}
		inline ll Query (char* s) {
			ll now = 0, len = strlen (s + 1), ans = 0;
			_for (i, 1, len) {
				now = nxt[now][s[i] - 'a'];
				for (ll p = now; p && ~end[p]; p = fail[p]) ans += end[p], end[p] = -1;
			}
			return ans;
		}
	};
}

例題

Keywords Search

板子題，

玄武密碼

在每個單詞結尾的節點往前跑，看哪個節點深度最高且被訪問過，

單詞

記錄每個點被訪問過多少次，但直接記錄時間會爆炸，

可以考慮延遲下傳訪問次數，

病毒

在 trie 樹上找一個包括根節點的環，能找到的話直接順著這個環不斷跑就可以構造出無限長的安全代碼，

最短母串

用哈希可以隨便殺啊！但是這是 AC 自動機題單，所以我要用 AC 自動機寫 DP（悲

\(f_{u, sta}\) 表示到節點 \(u\) 時，已經經過的字串狀態為 \(sta\) 時的最短字串，

然后不難發現直接暴力廣搜轉移即可，

文本生成器

\(f_{u, l, b}\) 表示到節點 \(u\) 時，已經經過 \(l\) 個字符，「是否已經出現過給定串」的答案為 \(b(b\in\{0, 1\})\) 時的可讀文本數量，

直接暴力廣搜轉移即可，

背單詞

首先建出整個 AC 自動機，然后查詢每個字串的答案，

查詢的程序有點說不太清，直接看碼罷，

注意每次查詢時把經過的節點標記一下，只能從標記過的節點轉移，

為啥要用線段樹啊，

貌似沒人有我這個方法？那貼一份代碼：

點擊查看代碼

const ll N = 3e5 + 10;

namespace ACAUTOMATON {
	class ACAutomaton {
	public:
		ll cnt = 0, nxt[N][26], jl[N], fail[N], f[N];
	public:
		inline void Clear () {
			_for (i, 0, cnt) {
				memset (nxt[i], 0, sizeof (nxt[i]));
				fail[i] = f[i] = jl[i] = 0;
			}
			cnt = 0;
			return;
		}
		inline void Insert (std::string s) {
			ll p = 0, len = s.length () - 1;
			_for (i, 0, len) {
				ll c = s[i] - 'a';
				if (!nxt[p][c]) nxt[p][c] = ++cnt;
				p = nxt[p][c];
			}
			return;
		}
		inline void Build () {
			std::queue <ll> q;
			_for (i, 0, 25) if (nxt[0][i]) fail[nxt[0][i]] = 0, q.push (nxt[0][i]);
			while (!q.empty ()) {
				ll u = q.front (); q.pop ();
				_for (i, 0, 25) {
					if (nxt[u][i]) fail[nxt[u][i]] = nxt[fail[u]][i], q.push (nxt[u][i]);
					else nxt[u][i] = nxt[fail[u]][i];
				}
			}
			return;
		}
		inline ll GetAns (std::string s, ll w) {
			ll p = 0, len = s.length () - 1, num = 0;
			_for (i, 0, len) {
				ll c = s[i] - 'a';
				jl[nxt[p][c]] = 1;
				if (jl[fail[nxt[p][c]]]) f[nxt[p][c]] = std::max (f[nxt[p][c]], f[fail[nxt[p][c]]]);
				num = std::max (num, f[nxt[p][c]]);
				p = nxt[p][c];
			}
			return f[p] = std::max (f[p], num + w);
		}
	};
}

namespace SOLVE {
	ll n, m, w[N], ans; std::string s[N];
	ACAUTOMATON::ACAutomaton ac;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline void In () {
		ac.Clear ();
		n = rnt (), ans = 0;
		_for (i, 1, n) {
			std::cin >> s[i], w[i] = rnt ();
			if (w < 0) continue;
			ac.Insert (s[i]);
		}
		return;
	}
	inline void Solve () {
		ac.Build ();
		_for (i, 1, n) {
			if (w[i] < 0) continue;
			ans = std::max (ans, ac.GetAns (s[i], w[i]));
		}
		return;
	}
	inline void Out () {
		printf ("%lld\n", ans);
		return;
	}
}

密碼

首先如果存在一個隨意填的位置，那么方案數至少為 \(52>42\)，例如：

7 2
good
day

*gooday 和 gooday* 中 * 的位置可以填 \(26\) 個字母，方案數至少為 \(2\times26=52\)，

那么只要不存在隨意填的位置，輸出就比較方便了，

設 \(f_{u, l, sta}\) 表示到節點 \(u\)，字串長度為 \(l\)，已經經過的字串狀態為 \(sta\) 時的最短字串，直接暴力廣搜轉移算出方案數，如果小于 \(42\) 就爆搜每種方案即可，

代碼比較惡心，貼一下：

點擊查看代碼

namespace ACAUTOMATON {
	class ACAutomaton {
	private:
		ll cnt = 0, tot = 1, nxt[N][26], fail[N], end[N], f[N][30][M], jl[N][30][M][2];
		class APJifengc { public: ll u, l, s; };
		std::pair <ll, ll> vis[30 * 45];
		std::vector <ll> answer;
		char temp[N];
	public:
		inline void Insert (char *s, ll id) {
			ll p = 0, len = strlen (s + 1);
			_for (i, 1, len) {
				ll c = s[i] - 'a';
				if (!nxt[p][c]) nxt[p][c] = ++cnt;
				p = nxt[p][c];
			}
			end[p] |= 1 << (id - 1);
			return;
		}
		inline void Build () {
			std::queue <ll> q;
			_for (i, 0, 25) if (nxt[0][i]) fail[nxt[0][i]] = 0, q.push (nxt[0][i]);
			while (!q.empty ()) {
				ll u = q.front (); q.pop ();
				_for (i, 0, 25) {
					if (nxt[u][i]) fail[nxt[u][i]] = nxt[fail[u]][i], end[nxt[u][i]] |= end[nxt[fail[u]][i]], q.push (nxt[u][i]);
					else nxt[u][i] = nxt[fail[u]][i];
				}
			}
			return;
		}
		inline ll BFS (ll target,ll m) {
			std::queue <APJifengc> q;
			ll ans = 0; f[0][0][0] = 1;
			q.push ((APJifengc){0, 0, 0});
			while (!q.empty ()) {
				ll u = q.front ().u, l = q.front ().l, s = q.front ().s; q.pop ();
				if (l > m) break;
				if (s == target && l == m) ans += f[u][l][s];
				_for (i, 0, 25) {
					ll v = nxt[u][i], ln = l + 1, st = s | end[v];
					if (!f[v][ln][st]) q.push ((APJifengc){v, ln, st});
					f[v][ln][st] += f[u][l][s];
				}
			}
			return ans;
		}
		inline ll DFS (ll u, ll l, ll s, ll target, ll m) {
			if (jl[u][l][s][0]) return jl[u][l][s][1];
			jl[u][l][s][0] = 1;
			if (l == m) return jl[u][l][s][1] = (s == target);
			_for (i, 0, 25) jl[u][l][s][1] |= DFS (nxt[u][i], l + 1, s | end[nxt[u][i]], target, m);
			return jl[u][l][s][1];
		}
		inline void PrintAns (ll u, ll l, ll s, ll m) {
			if (!jl[u][l][s][1]) return;
			if (l == m) { puts (temp + 1); return; }
			_for (i, 0, 25) temp[l + 1] = i + 'a', PrintAns (nxt[u][i], l + 1, s | end[nxt[u][i]], m);
			return;
		}
	};
}

namespace SOLVE {
	ll n, m, ans; char s[20];
	ACAUTOMATON::ACAutomaton ac;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline void In () {
		m = rnt (), n = rnt ();
		_for (i, 1, n) {
			scanf ("%s", s + 1);
			ac.Insert (s, i);
		}
		return;
	}
	inline void Solve () {
		ac.Build ();
		ans = ac.BFS ((1 << n) - 1, m);
		if (ans <= 42) ac.DFS (0, 0, 0, (1 << n) - 1, m);
		return;
	}
	inline void Out () {
		printf ("%lld\n", ans);
		if (ans <= 42) ac.PrintAns (0, 0, 0, m);
		return;
	}
}

禁忌

有點像 GT 考試

設 \(f_{i, u}\) 表示長度為 \(i\)，到了節點 \(u\) 的串的期望傷害，

\[f_{i, u} = \frac{1}{alphabet}\sum_{son_{v,c} = u} f_{i - 1,v} \]

但是 \(len\le10^9\)，不能直接轉移，

于是套一下矩陣乘法就好了，

碼：

點擊查看代碼

namespace MATRIX {
	class Matrix {
	private:
		ll n; ldb a[N][N];
	public:
		inline ldb* operator [] (ll x) { return a[x]; }
		inline void Init (ll nn) { n = nn, memset (a, 0, sizeof (a)); return; }
		inline Matrix operator * (Matrix another) const {
			Matrix ans; ans.Init (n);
			_for (i, 0, n) _for (j, 0, n) _for (k, 0, n)
				ans[i][j] += a[i][k] * another[k][j];
			return ans;
		}
		inline void Print () {
			printf ("%lld\n", n);
			_for (i, 0, n) { _for (j, 0, n) printf ("%Lf ", a[i][j]); puts (""); }
			puts ("");
			return;
		}
	};
}

namespace ACAUTOMATON {
	class ACAutomaton {
	private:
		ll cnt = 0, nxt[N][26], fail[N], end[N];
	public:
		inline void Insert (std::string s) {
			ll p = 0, len = s.length () - 1;
			_for (i, 0, len) {
				ll c = s[i] - 'a';
				if (!nxt[p][c]) nxt[p][c] = ++cnt;
				p = nxt[p][c];
			}
			end[p] = 1;
			return;
		}
		inline ll Build (ll alphabet) {
			std::queue <ll> q;
			_for (i, 0, alphabet - 1) if (nxt[0][i]) fail[nxt[0][i]] = 0, q.push (nxt[0][i]);
			while (!q.empty ()) {
				ll u = q.front (); q.pop ();
				_for (i, 0, alphabet - 1) {
					if (nxt[u][i]) fail[nxt[u][i]] = nxt[fail[u]][i], q.push (nxt[u][i]);
					else nxt[u][i] = nxt[fail[u]][i];
				}
				end[u] |= end[fail[u]];
			}
			return cnt;
		}
		inline MATRIX::Matrix GetMatrix (ll alphabet) {
			MATRIX::Matrix ma; ma.Init (cnt + 1);
			_for (i, 0, cnt) {
				_for (j, 0, alphabet - 1) {
					if (end[nxt[i][j]]) ma[i][0] += 1.0 / (ldb)(alphabet), ma[i][cnt + 1] += 1.0 / (ldb)(alphabet);
					else ma[i][nxt[i][j]] += 1.0 / (ldb)(alphabet);
				}
			}
			ma[cnt + 1][cnt + 1] = 1.0;
			return ma;
		}
	};
}

namespace SOLVE {
	ll n, m, len, alphabet;
	std::string s[N];
	MATRIX::Matrix ans;
	ACAUTOMATON::ACAutomaton ac;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}

	inline MATRIX::Matrix FastPow (MATRIX::Matrix a, ll b) {
		MATRIX::Matrix an; an.Init (m);
		_for (i, 0, m) an[i][i] = 1.0;
		while (b) {
			if (b & 1) an = an * a;
			a = a * a, b >>= 1;
		}
		return an;
	}

	inline void In () {
		n = rnt (), len = rnt (), alphabet = rnt ();
		_for (i, 1, n) {
			std::cin >> s[i];
			ac.Insert (s[i]);
		}
		return;
	}
	inline void Solve () {
		m = ac.Build (alphabet) + 1;
		MATRIX::Matrix ma = ac.GetMatrix (alphabet);
		ans.Init (m), ans[0][0] = 1.0;
		ma = FastPow (ma, len), ans = ans * ma;
		return;
	}
	inline void Out () {
		printf ("%.10Lf\n", ans[0][m]);
		return;
	}
}

\[\Huge{\mathfrak{The\ End}} \]

本文來自博客園，作者：K8He，轉載請注明原文鏈接：https://www.cnblogs.com/Keven-He/p/ACAutomaton.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551738.html

標籤：其他

上一篇：【光伏預報/太陽能預報】上海道寧與Solargi為您提供開發地理資料庫模擬工具和網路服務

下一篇：返回列表