一、题目：

二、思路：

由于刚学了AC自动机，所以这个题就用AC自动机写吧。

先来回顾AC自动机的基本功能，类比KMP，AC自动机能求出每个单词在文章中的出现位置，对吧？

那么看这个题，如果我们将单词在文章中出现的位置记录下来，变成区间\([l,r]\)，那么这个题就变成了区间覆盖问题。即求出文章中最长的一段前缀，这段前缀上任意一个位置不能被超过一个区间覆盖，也不能不被覆盖。

那么我们对于一个区间\([l,r]\)，将l连一条到r的有向边，BFS搜一遍即可。

注：邻接表不要用vector，我被卡常了10几回！！

三、代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long long#define FILEIN(s) freopen(s".in","r",stdin)#define FILEOUT(s) freopen(s".out","w",stdout)#define mem(s,v) memset(s,v,sizeof(s))using namespace std;inline LL read(void){    LL x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return f*x;}const int maxn=1500000;int n,m,sz,trie[maxn][30],fail[maxn],Len[maxn];int tag[maxn];bool vis[maxn];char S[maxn];int head[maxn],tot;struct Node{    int y,next;}e[maxn];inline void connect(int x,int y){    e[++tot].y=y;e[tot].next=head[x];    head[x]=tot;}inline void insert(char *s){    int p=0,len=strlen(s+1);    for(register int i=1;i<=len;++i){        if(!trie[p][s[i]-'a'+1])trie[p][s[i]-'a'+1]=++sz;        p=trie[p][s[i]-'a'+1];    }    tag[p]++;    Len[p]=len;}inline void bfs(void){    queue
         
          q; for(register int i=1;i<=26;++i){ if(trie[0][i])q.push(trie[0][i]),fail[trie[0][i]]=0; } while(q.size()){ int x=q.front();q.pop(); for(register int i=1;i<=26;++i){ if(trie[x][i])fail[trie[x][i]]=trie[fail[x]][i],q.push(trie[x][i]); else trie[x][i]=trie[fail[x]][i]; } }}inline int query(char *s){ int len=strlen(s+1),ret=0; int p=0; for(register int i=1;i<=len;++i){ p=trie[p][s[i]-'a'+1]; for(register int t=p;t;t=fail[t]){ if(tag[t]){ int l=i-Len[t]+1; int r=i; connect(l,r); } } } // for(register int i=0;i
          
           <
           
            <<" "; queue
            
             q; q.push(1); mem(vis,0); vis[1]=true; while(q.size()){ int l=q.front();q.pop(); for(register int i=head[l];i;i=e[i].next){ int r=e[i].y; if(vis[r+1])continue; ret=max(ret,r); q.push(r+1); vis[r+1]=true; } } return ret;}int main(){ n=read();m=read(); for(register int i=1;i<=n;++i){ scanf("%s",S+1); insert(S); } bfs(); while(m--){ mem(e,0);mem(head,0);tot=0; scanf("%s",S+1); printf("%d\n",query(S)); } return 0;}