题意：给你n个字符串，再给你一个匹配串，问你对于匹配串的每一个字符，至少在后面添加几个字符，使得之前给的n的字符串中有添加后的串的后缀

解题思路：因为是要当多模式匹配，想到用AC自动机，因为要至少添加几个字符，所以我们把n个给定的字符串存在trie图中，把每个串结尾点标记，从结尾点开始往前bfs，这样可以算到，当前要匹配的字符串在trie图中匹配到某个位置后，至少需要多少步能走到结尾点，具体看代码

代码

#include
     
      using namespace std;const int maxn=400500;const int inf=0x3f3f3f3f;int trie[maxn][26];int fail[maxn],tot;int flag[maxn];int dist[maxn];int n;vector
      
       v[maxn];set
       
        s;char t[maxn];void init(){    memset(trie,0,sizeof(trie));tot=0;    memset(fail,0,sizeof(fail));    memset(flag,0,sizeof(flag));    memset(dist,inf,sizeof(dist));    s.clear();}void build_trie(char *str){    int root=0;    int len=strlen(str);    for(int i=0;i
        

q; for(int i=0;i<26;i++) { if(trie[0][i]!=0) q.push(trie[0][i]); } while(!q.empty()) { int now=q.front();q.pop(); if(flag[fail[now]]) { flag[now]=1;s.insert(now);//这里重点，如果一个点的fail指向某个结尾点，那么它也是结尾点；fail的定义是指向当前串的最长后缀 } for(int i=0;i<26;i++) { if(!trie[now][i]) { trie[now][i]=trie[fail[now]][i]; continue; } fail[trie[now][i]]=trie[fail[now]][i]; q.push(trie[now][i]); } }}void bfs(){ for(int i=0;i<=tot;i++) v[i].clear(); for(int i=0;i<=tot;i++) for(int j=0;j<26;j++) v[trie[i][j]].push_back(i);//把trie图反过来存 queue

q; for(set

::iterator it=s.begin();it!=s.end();it++) { q.push(*it);dist[*it]=0;//结尾点成开始搜索点 } while(!q.empty()) { int now=q.front();q.pop(); for(int i=0;i