#include
     
      using namespace std;#define ll long longint ans=0;const int maxnode=1e6+7;  const int sigma_size=26;struct AC_Automata  {      int ch[maxnode][sigma_size];      int val[maxnode];   // 每个字符串的结尾结点都有一个非0的val      int f[maxnode];     // fail函数      int last[maxnode];  // last[i]=j表j节点表示的单词是i节点单词的后缀，且j节点是单词节点      int sz;        //初始化0号根节点的相关信息      void init()      {          sz=1;          memset(ch[0],0,sizeof(ch[0]));          val[0]=0;      }        void insert(char *s,int v)      {          int u=0;          for(int i=0; s[i]; i++)          {              int id=s[i]-'a';              if(ch[u][id]==0)              {                  ch[u][id]=sz;                  memset(ch[sz],0,sizeof(ch[sz]));                  val[sz++]=0;              }              u=ch[u][id];          }          val[u]+=v;      }         void getFail()      {          queue
      
        q;          last[0]=f[0]=0;          for(int i=0; i
       
        0      void print(int i)      {          if(i)          {  			ans+=val[i];			val[i]=0;						print(last[i]);          }      }        void find(char *s)      {          int j=0;//j:trie树中的节点编号          for(int i=0; s[i]; i++)          {              int id=s[i]-'a';              while(j && ch[j][id]==0) j=f[j];//ch[j][id]:第j个节点的id字母子节点编号             j=ch[j][id];              if(val[j]) print(j);              else if(last[j]) print(last[j]);          }      }    };  AC_Automata ac;  const int maxn=1e6+7;char ori[maxn];char tar[maxn];int main(){	int t;	scanf("%d",&t);	while(t--){		ans=0;		ac.init();		int n;		scanf("%d",&n);			for(int i=1;i<=n;i++){			scanf("%s",tar);			ac.insert(tar,1);		}			ac.getFail();		scanf("%s",ori);		ac.find(ori);		printf("%d\n",ans);	}}
       
      
     

自动机的英文念起来好中二啊，

自动机就是trie树和kmp算法的组合，多模板匹配的首选算法

两种快乐的算法重叠在一起，就有了自动机（

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

贴一个轻量化的板子，原题HDU3065

#include
     
      using namespace std;#define ll long longconst int maxn=2e6+7;const int maxm=55;const int maxnode=1010*51;const int sigma=128-30;int n,m;int vis[1010];char word[1010][55];char ori[maxn];struct automata{	int ch[maxnode][sigma];	int val[maxnode];	int f[maxnode];	int sz;	int newnode(){		memset(ch[sz],0,sizeof(ch[sz]));		f[sz]=val[sz]=0;		return sz++;	}	void init(){		memset(val,0,sizeof(val));		sz=0;		newnode();	}	void insert(char s[],int v){			int u=0;		for(int i=0;s[i];i++){			int &x=ch[u][s[i]-30];			u=x?x:x=newnode();			}		val[u]=v;	}	void build(){		queue
      
       q;		q.push(0);			while(!q.empty()){			int u=q.front();q.pop();			for(int i=0;i