文本查找

發布時間: 2017年7月5日 00:10?? 最后更新: 2017年7月5日 13:47?? 時間限制: 1500ms?? 內存限制: 128M

描述

給定m種兩兩不同的關鍵詞，并給定一段文本，問這段文本中有幾種關鍵詞出現（一種關鍵詞出現多次只算一次）。

輸入

多組輸入數據。
每組數據第一行一個正整數m，表示有m個關鍵詞。
接下來m行每行一個關鍵詞，關鍵詞僅包含小寫字母。
最后一行為文本，僅包含小寫字母。
每組數據保證關鍵詞總長度不超過106，文本不超過106。
總字符輸入量不超過107。

輸出

對于每組數據，輸出一行一個整數，表示答案。

樣例輸入1?復制 3 a aa b aa 樣例輸出1 2 AC自動機的裸題，這里要說明的一點就是，一種關鍵詞出現多次只能算一次，這樣的話，我們就可以在一個關鍵詞匹配完成后，在Trie樹相關位置打上一個標記，防止下次重復計數。

代碼:

#include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAXN = 1e6+7;; #define LETTER 26 struct Trie{int num, fail,match;int next[LETTER]; }pool[MAXN]; Trie* const trie = pool + 1; int cnt; void init(){cnt = 0;memset(pool, 0, 2 * sizeof(Trie));trie[0].fail = -1; } inline int convert(char c){return c - 'a'; } void build() {queue<int> q; q.push(0);while (!q.empty()){int t = q.front(); q.pop();for (int i = 0; i < LETTER; i++){int &cur = trie[t].next[i];if (cur){q.push(cur);trie[cur].fail = trie[trie[t].fail].next[i];trie[cur].match = trie[cur].num ? cur :trie[trie[cur].fail].match;}else cur = trie[trie[t].fail].next[i];}} } int search(char *s) {int ret = 0, cur = 0;for (int i = 0; s[i]; i++){cur = trie[cur].next[convert(s[i])];for (int temp = trie[cur].match; temp;temp = trie[trie[temp].fail].match){ret += trie[temp].num;if(!trie[temp].num) break;trie[temp].num = 0;}}return ret; } void insert(char s[]){int cur = 0;for(int i = 0;s[i];i++){int &pos = trie[cur].next[convert(s[i])];if(!pos){pos = ++cnt;memset(&trie[cnt],0,sizeof(Trie));}cur = pos;}trie[cur].num ++; } char pat[MAXN]; char str[MAXN]; int main(){int m;while(~scanf("%d",&m)){init();while(m--){scanf(" %s",pat);insert(pat);}build();scanf(" %s",str);int ans = search(str);printf("%d\n",ans);} }

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的2017西安交大ACM小学期 文本查找[AC自动机]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。