自动搬运

查看原文

来自洛谷，原作者为

	itisover 招募ACM队友

搬运于2025-08-24 22:08:30，当前版本为作者最后更新于2021-02-08 10:19:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

极简思路：

先跑一边AC自动机，处理出 fail 数组，然后再把文本串匹配一下，可以获得 vis 数组，代表着 trie 树上的这个点是文本串的前缀。最后只需要再每个模式串跑一遍 trie 树，就可以得到最长的公共前缀长度了。

#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;
}