題目鏈接：點擊查看

題目大意：給出n個長度不超過50的模式串，再給出一個長度不超過1e6的主串，問模式串在主串中出現過多少次

題目分析：一開始我以為是求n次KMP，后來才知道這樣做的時間復雜度是O(LM+N)，L是模式串個數，M是主串長度，N是模式串總長度，如果是這樣做必然會超時，于是就接觸了AC自動機這個算法，是個注明的多模匹配算法，可以再O(M+N)的時間復雜度下完成上述任務

這里插個眼，配圖配的很好的一個博客：

https://blog.csdn.net/bestsort/article/details/82947639#commentBox

那么對于這個題來說就是一個AC自動機的模板題了，直接掛代碼吧，重要的是理解fail指針，和如何利用fail指針進行匹配的過程

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef unsigned long long ull;typedef long long LL;const int inf=0x3f3f3f3f;const int N=(1e4+100)*50;int trie[N][26];char s[N*2];int cntword[N];int cnt;int fail[N];void insert_word() {int len=strlen(s);int pos=0;for(int i=0;i<len;i++){int to=s[i]-'a';if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];}cntword[pos]++; }void getfail() {queue<int>q;for(int i=0;i<26;i++){if(trie[0][i]){fail[trie[0][i]]=0;q.push(trie[0][i]);}}while(!q.empty()){int cur=q.front();q.pop();for(int i=0;i<26;i++){if(trie[cur][i]){fail[trie[cur][i]]=trie[fail[cur]][i];q.push(trie[cur][i]);}elsetrie[cur][i]=trie[fail[cur]][i];}} }int search_word() {int len=strlen(s);int ans=0;int pos=0;for(int i=0;i<len;i++){pos=trie[pos][s[i]-'a'];for(int j=pos;j&&cntword[j]!=-1;j=fail[j]){ans+=cntword[j];cntword[j]=-1;}}return ans; }void init() {cnt=0;memset(cntword,0,sizeof(cntword));memset(trie,0,sizeof(trie)); }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){init();int n;scanf("%d",&n);while(n--){scanf("%s",s);insert_word();}getfail();scanf("%s",s);printf("%d\n",search_word());}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 2222 Keywords Search(AC自动机)的全部內容，希望文章能夠幫你解決所遇到的問題。

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