題意:

　　求n個模板串在匹配串中出現了幾個.

SOL:

　　反正就是模板啦...似乎比KMP都簡單----這么說似乎有點不道德...畢竟先看的KMP而他們并沒有什么不同...

　　貌似自己的理解和他們畫的圖還是有些出入......不虛慢慢看...

　　然后就是特殊一點的一個last數組,可以比較迅速地找到包含的子串.

　　這個題目會出現相同的模板...沒看懂老人家開map的意圖,第一遍用vector打,然后這種統計數量不是直接開個num記錄數量就好了嗎...

　　然而為毛我的num比開vector還慢呢...

　　

/*========================================================================== # Last modified: 2016-03-02 19:00 # Filename: a.cpp # Description: ==========================================================================*/ #define me AcrossTheSky #include <cstdio> #include <cmath> #include <ctime> #include <string> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <set> #include <map> #include <stack> #include <queue> #include <vector> #define lowbit(x) (x)&(-x) #define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++) #define FORP(i,a,b) for(int i=(a);i<=(b);i++) #define FORM(i,a,b) for(int i=(a);i>=(b);i--) #define ls(a,b) (((a)+(b)) << 1) #define rs(a,b) (((a)+(b)) >> 1) #define getlc(a) ch[(a)][0] #define getrc(a) ch[(a)][1] #define maxn 1000200 #define maxm 100000 #define maxc 30 #define pi 3.1415926535898 #define _e 2.718281828459 #define INF 1070000000 using namespace std; typedef long long ll; typedef unsigned long long ull; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*==================split line==================*/ char temp[maxn],s[60]; int ch[500005][maxc],f[500005],last[500005]; vector<int> val[500005]; int sz,ans; void reset(){ sz=1; ans=0; memset(ch,0,sizeof(ch)); memset(last,0,sizeof(last));memset(val,0,sizeof(val)); memset(f,0,sizeof(f)); } int idx(char c){return c-'a';} void insert(char *s,int v){int u=0,len=strlen(s);FORP(i,0,len-1){int c=idx(s[i]);if (!ch[u][c]) {while(val[sz].size()) val[sz].pop_back();ch[u][c]=sz++;}u=ch[u][c];}val[u].push_back(v); } void add(int j){while(val[j].size()){ ans+=val[j].size(); while (val[j].size()) val[j].pop_back();j=last[j];} } void find(char *T){int n=strlen(T);int j=0;FORP(i,0,n-1){int c=idx(T[i]);j=ch[j][c];if (val[j].size()) add(j);else if(last[j]) add(last[j]);} } void getfail(){queue<int>q;f[0]=0;FORP(c,0,maxc-1){int u=ch[0][c];if (u) { f[u]=0; last[u]=0; q.push(u);}}while (!q.empty()){int r=q.front(); q.pop();FORP(c,0,maxc-1){int u=ch[r][c];if (!u) {ch[r][c]=ch[f[r]][c]; continue;}q.push(u);int v=f[r];while (v && !ch[v][c]) v=f[v];f[u]=ch[v][c];last[u]=val[f[u]].size()?f[u]:last[f[u]];}} } int main(){int cas; read(cas); while (cas--){ reset();int n; read(n);FORP(i,1,n){scanf("%s",s);insert(s,i);}scanf("%s",temp);getfail();find(temp);printf("%d\n",ans);} }

?

轉載于:https://www.cnblogs.com/YCuangWhen/p/5237322.html

總結

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

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