贴份模板
胡大神和崔大神的组合模板
#include#include #include #include #include #include #include #include #include using namespace std;#define N 1000010#define LL long long#define INF 0xfffffff#define maxch 26const double eps = 1e-8;const double pi = acos(-1.0);const double inf = ~0u>>2;const int child_num = 26;char ss[N];class ACAutomation{ private: int ch[N][maxch]; int val[N]; int fail[N]; int Q[N]; int id[128]; int sz; // int dp[2][N][1<<10]; public: void init() { fail[0] = 0; for(int i = 0 ; i < child_num; i++) id[i+'a'] = i; } void reset()//初始化 { memset(ch[0],0,sizeof(ch[0])); memset(val,0,sizeof(val)); sz = 1; } void insert(char *a,int key)//建立trie树 { int p = 0; for( ; *a ; a++) { int c = id[*a]; if(ch[p][c]==0) { memset(ch[sz],0,sizeof(ch[sz])); val[sz] = 0; ch[p][c] = sz++; } p = ch[p][c]; } val[p] += key; } void construct()//构建fail指针 { int head = 0,tail = 0,i; for(i = 0 ;i < child_num ; i++) { if(ch[0][i]) { fail[ch[0][i]] = 0; Q[tail++] = ch[0][i]; } } while(head!=tail) { int u = Q[head++]; for(i = 0 ;i < child_num ;i ++) { if(ch[u][i]!=0) { Q[tail++] = ch[u][i]; fail[ch[u][i]] = ch[fail[u]][i]; } else ch[u][i] = ch[fail[u]][i]; } } } int work(char *s) { int k = strlen(s); int p = 0,ans = 0; for(int i = 0; i < k ; i++) { int d = s[i]-'a'; p = ch[p][d]; int tmp = p; while(tmp!=0&&val[tmp]!=0) { ans+=val[tmp]; val[tmp] = 0; tmp = fail[tmp]; } } return ans; }}ac;int main(){ int t,n; char word[55]; ac.init(); cin>>t; while(t--) { cin>>n; ac.reset(); while(n--) { scanf("%s",word); ac.insert(word,1); } ac.construct(); scanf("%s",ss); printf("%d\n",ac.work(ss)); } return 0;}