本文共 1574 字，大约阅读时间需要 5 分钟。
题意：问前面给的所有串在最后一个串出现的次数
思路：这道题是AC自动机入门必做的题，所以没什么好说的，是个模版题，推荐一个大神写的详解，不懂得可以看一看，反正我是看他的稍稍懂了点
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- const int inf=0x3f3f3f3f;
- const int maxn=500010;
- const int N=26;
- struct node{
- node *fail;
- node *next[N];
- int num;
- node(){
- fail=NULL;
- num=0;
- memset(next,NULL,sizeof(next));
- }
- }*q[maxn];
- char str1[60],str2[1000010];
- int head,tail;
- void insert_Trie(char *str,node *root){
- node *p=root;
- int i=0;
- while(str[i]){
- int id=str[i]-'a';
- if(p->next[id]==NULL) p->next[id]=new node();
- p=p->next[id];i++;
- }
- p->num++;
- }
- void build_ac(node *root){
- root->fail=NULL;
- q[head++]=root;
- while(head!=tail){
- node *temp=q[tail++];
- node *p=NULL;
- for(int i=0;i<N;i++){
- if(temp->next[i]!=NULL){
- if(temp==root) temp->next[i]->fail=root;
- else{
- p=temp->fail;
- while(p!=NULL){
- if(p->next[i]!=NULL){
- temp->next[i]->fail=p->next[i];
- break;
- }
- p=p->fail;
- }
- if(p==NULL) temp->next[i]->fail=root;
- }
- q[head++]=temp->next[i];
- }
- }
- }
- }
- int query(node *root){
- int i=0,ans=0;
- node *p=root;
- while(str2[i]){
- int id=str2[i]-'a';
- while(p->next[id]==NULL&&p!=root) p=p->fail;
- p=p->next[id];
- p=(p==NULL)?root:p;
- node *temp=p;
- while(temp!=root&&temp->num!=-1){
- ans+=temp->num;
- temp->num=-1;
- temp=temp->fail;
- }
- i++;
- }
- return ans;
- }
- int main(){
- int T,n;
- scanf("%d",&T);
- while(T--){
- node *root=new node();
- head=tail=0;
- scanf("%d",&n);
- for(int i=0;i<n;i++){
- scanf("%s",str1);
- insert_Trie(str1,root);
- }
- build_ac(root);
- scanf("%s",str2);
- int ans=query(root);
- printf("%d\n",ans);
- }
- return 0;
- }
转载地址：http://giali.baihongyu.com/