#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5,M=1e5+5;
int n,lent;
int trie[N][26],tot,fail[N],End[N];
int vis[N];
char tmp[M][105],t[N];
queue<int> q;
void ins(char *str){
  int len=strlen(str),p=0;
  for(int i=0;i<len;i++){
    int ch=str[i]-'A';
    if(!trie[p][ch]) trie[p][ch]=++tot;
    p=trie[p][ch];
  }
  End[p]++;
}
void build(){
  for(int i=0;i<26;i++) if(trie[0][i]) q.push(trie[0][i]),fail[trie[0][i]]=0;
  while(!q.empty()){
    int u=q.front();q.pop();
    for(int i=0;i<26;i++){
      if(trie[u][i]) fail[trie[u][i]]=trie[fail[u]][i],q.push(trie[u][i]);
      else trie[u][i]=trie[fail[u]][i];
    }
  }
  int p=0;
  for(int i=0;i<lent;i++){
    p=trie[p][t[i]-'A'];
    for(int k=p;k&&!vis[k];k=fail[k]) vis[k]=1;
  }
}
int Query(char *str){
  int len=strlen(str),p=0,res=0;
  for(int i=0;i<len;i++){
    p=trie[p][str[i]-'A'];
    if(vis[p]) res=i+1;
  }
  return res;
}
int main(){
  scanf("%d%d",&lent,&n);
  scanf("%s",t);
  for(int i=1;i<=n;i++){
    scanf("%s",tmp[i]);
    ins(tmp[i]);
  }
  build();
  for(int i=1;i<=n;i++){
    printf("%d\n",Query(tmp[i]));
  }
  return 0;
}

首先我们发现这题是一道裸的Aho-Corasick自动机。

经典做法是对于每个节点维护一个集合，记录走到这个点的时候将有哪些模式串的答案被更新。同时根据AC自动机的特性，更新节点u的同时还要更新节点fail[u]。这种做法能勉强通过40%的数据。

事实上，对于每个节点，我们可以只记录一个布尔值vis，代表该节点是否在匹配过程中被访问过，访问节点u时仍然需要递归地去访问fail[u]。可以保证每个节点至多被访问1次。与此同时，每次的insert过程中，我们记录：对于字符串i，匹配到长度j的节点编号match[i][j]。接下来对于每个字符串，我们在[0, 100]进行二分查找，每次检查vis[match[i][mid]]是否为真。总的时间复杂度是O(M|S|+N+Mlog100)，可以承受。

这时候其实还有一个小小的优化……
我们自行生成一个N=10^6的随机数据，会发现对于（几乎）所有的模式串，答案都等于该模式串的长度。由于字符集很小，我们可以认为，对于一个随机的数据，当母串足够长时，所有的模式串几乎都能在母串中找到匹配。故此，当N>10^6时，我采取了这样的策略：对于每个模式串，直接输出它的长度。

……然后就过了……最大数据280ms……23333333

后缀自动机裸题，但注意只匹配文字的前缀，不用再往pre上转移
由于n很大，数组开不出来，需要采用楼下神犇的方法过最后一个点Orz
http://blog.leanote.com/post/okami/vijos