【CTSC2012】熟悉的文章

题面

https://www.luogu.org/problem/P4022

题解

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#define ri register int
#define N 1100050
#define INF 998244353
using namespace std;
vector<int> son[N];
int n,m,l;
string s,ts;
int que[N],head,tail;

struct SAM {
  int ff[N<<1],len[N<<1];
  int ch[N<<1][3];
  int g[N<<1],f[N<<1];
  int las,tot;
  void init(){
    las=tot=1;
  }
  void extend(int c) {
    int np=++tot,p=las; las=np;
    len[np]=len[p]+1;
    while (p && !ch[p][c]) ch[p][c]=np,p=ff[p];
    if (!p) ff[np]=1;
    else {
      int q=ch[p][c];
      if (len[p]+1==len[q]) ff[np]=q;
      else {
        int nq=++tot;
        for (ri i=0;i<3;i++) ch[nq][i]=ch[q][i]; ff[nq]=ff[q];
        len[nq]=len[p]+1;
        ff[np]=ff[q]=nq;
        while (p && ch[p][c]==q) ch[p][c]=nq,p=ff[p];
      }
    }
  }
  bool match(int L0) {
    int now=1,cc=0;
    tail=1; head=0;
    for (ri i=0;i<=l;i++) f[i]=0,g[i]=f[i]-i;
    for (ri i=1;i<=l;i++) {
      if (ch[now][ts[i]-'0']) {
        cc++;
        now=ch[now][ts[i]-'0'];
      }
      else {
        while (now && !ch[now][ts[i]-'0']) now=ff[now];
        if (!now) {
          now=1; cc=0;
          continue;
        }
        else {
          cc=len[now]+1;
          now=ch[now][ts[i]-'0'];
        }
      }
      if (i>=L0) {
        while (tail<=head && g[i-L0]>=g[que[head]]) head--;
        que[++head]=i-L0;
      }
      while (tail<=head && que[tail]<i-cc) tail++;
      if (i-cc<=que[tail] && que[tail]<=i-L0 && tail<=head) f[i]=g[que[tail]]+i; else f[i]=0;
      if (f[i]<f[i-1]) f[i]=f[i-1];
      g[i]=f[i]-i;
    }
    //printf("limit=%d
",L0);
    //for (ri i=1;i<=l;i++) {
      //printf("%d %d
",i,f[i]);
    //}
    //puts("");
    for (ri i=1;i<=l;i++) if ((f[i]*1.0)/(l*1.0)>=0.90) return 1;
    return 0;
  }
} sam;

int main(){
  //freopen("10.in","r",stdin);
  cin>>n>>m;
  s="2";
  for (ri i=1;i<=m;i++) cin>>ts,s=s+ts+"2";
  sam.init();
  l=s.size();
  for (ri i=0;i<l;i++) sam.extend(s[i]-'0');
  for (ri i=1;i<=n;i++) {
    cin>>ts; l=ts.size();
    ts="#"+ts;
    int lb=1,rb=l;
    int ans=0;
    while (lb<=rb) {
      int mid=(lb+rb)/2;
      if (sam.match(mid)) ans=mid,lb=mid+1; else rb=mid-1;
    }
    cout<<ans<<endl;
  }
}