\(Trie\)树+\(DP\)

我们只需要做一个存在性dp就好了

对于每一个字符串，我们设\(f[i]\)表示从\(1\)到\(i\)位是否能被完全匹配

首先\(f[0]=1\)，之后我们对于每一个\(f[i]=1\)我们都可以往下匹配

具体的匹配方法自然是丢到\(Trie\)树上去，从\(i\)这位开始，一旦遇到一个结束标记就将这个结束标记对应位置的\(f[x]=1\)，之后就可以了

#include
    
     #include
     
      #include
      
       #define re register#define maxn 1000005char S[maxn];int son[505][27],flag[505];char T[11];int cnt;bool f[maxn];inline int read(){    char c=getchar();    int x=0;    while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9')      x=(x<<3)+(x<<1)+c-48,c=getchar();    return x;}int n,m;inline void ins(){    int len=strlen(T+1);    int now=0;    for(re int i=1;i<=len;i++)    {        if(!son[now][T[i]-'a']) son[now][T[i]-'a']=++cnt;        now=son[now][T[i]-'a'];    }    flag[now]=1;}inline void check(int x,int len){    int now=0;    for(re int i=x;i<=len;i++)    {        if(!son[now][S[i]-'a']) return;        now=son[now][S[i]-'a'];        if(flag[now]) f[i]=1;    }}int main(){    n=read();m=read();    for(re int i=1;i<=n;i++)    {        scanf("%s",T+1);        ins();    }    for(re int t=1;t<=m;t++)    {        scanf("%s",S+1);        memset(f,0,sizeof(f));        f[0]=1;        int len=strlen(S+1);        int ans=0;        for(re int i=0;i<=len;i++)        {            if(!f[i]) continue;            ans=i;            check(i+1,len);        }        if(!ans) puts("-1");        else printf("%d",ans),putchar(10);    }    return 0;}