bzoj3277串&&bzoj3473字符串&&bzoj2780[Spoj]8093SevenkLoveOimaster——广义后缀自动机

#include
#include
#include<string>//
#include
#define ll long long
using namespace std;
int Mx(int a,int b){return a>b?a:b;}
const int N=1e5+5,M=N<<1,K=27;//<<1
int n,k,go[M][K],l[M],fa[M],tot=1;
int tx[M],q[M],ans[M],ct[M],vis[M];
int cz(int p,int w)
{
  int q=go[p][w],nq=++tot;l[nq]=l[p]+1;
  fa[nq]=fa[q];fa[q]=nq;
  memcpy(go[nq],go[q],sizeof go[q]);
  for(;p&&go[p][w]==q;p=fa[p])go[p][w]=nq;
  return nq;
}
int ins(int p,int w)
{
  if(go[p][w])
    {
      int q=go[p][w];
      if(l[q]==l[p]+1)return go[p][w];
      else return cz(p,w);//////
    }
  else
    {
      int np=++tot;l[np]=l[p]+1;
      for(;p&&!go[p][w];p=fa[p])go[p][w]=np;
      if(!p)fa[np]=1;
      else
    {
      int q=go[p][w];
      if(l[q]==l[p]+1)fa[np]=q;
      else fa[np]=cz(p,w);
    }
      return np;
    }
}
void Rsort(int mxn)
{
  for(int i=1;i<=tot;i++)tx[l[i]]++;
  for(int i=1;i<=mxn;i++)tx[i]+=tx[i-1];
  //  for(int i=tot;i;i--)q[tx[l[i]]--]=i;
  for(int i=1;i<=tot;i++)q[tx[l[i]]--]=i;
}
string ch[N]; int len[N];
int main()
{
  scanf("%d%d",&n,&k); char tp[N]; int mxn=0;
  for(int i=1,d;i<=n;i++)
    {
      scanf("%s",tp);len[i]=strlen(tp);mxn=Mx(mxn,len[i]);
      ch[i]=tp;
    }
  for(int i=1;i<=n;i++)
    for(int lm=len[i],pr=1,j=0;j)
      pr=ins(pr,ch[i][j]-'a'+1);
  for(int i=1;i<=n;i++)
    for(int lm=len[i],cr=1,j=0;j)
      {
    cr=go[cr][ch[i][j]-'a'+1];
    for(int p=cr;p&&vis[p]!=i;p=fa[p])
      ct[p]++,vis[p]=i;
      }
  Rsort(mxn);
  for(int i=2,d;i<=tot;i++)
    {d=q[i];ans[d]=ans[fa[d]]+(ct[d]>=k?l[d]-l[fa[d]]:0);}//
  for(int i=1;i<=n;i++)
    {
      ll prn=0;
      for(int lm=len[i],cr=1,j=0;j)
    {
      cr=go[cr][ch[i][j]-'a'+1];
      prn+=ans[cr];
    }
      printf("%lld ",prn);
    }
  puts("");return 0;
}

#include
#include
#include
#include<string>
using namespace std;
int const xn=2e5+5;
const int N=1e4+5,M=2e5+5,N2=4e5+5,K=27;
int n,go[M][K],fa[M],l[M],ct[M],tot=1;
string s[N];int len[N],vis[M];
int cz(int p,int w)
{
  int q=go[p][w],nq=++tot; l[nq]=l[p]+1;/////////l[p]+1 not l[q]+1!!!!!
  fa[nq]=fa[q];fa[q]=nq;
  memcpy(go[nq],go[q],sizeof go[q]);
  for(;p&&go[p][w]==q;p=fa[p])go[p][w]=nq;
  return nq;
}
int ins(int p,int w)
{
  if(go[p][w])
    {
      int q=go[p][w];
      if(l[q]==l[p]+1)return q; else return cz(p,w);
    }
  else
    {
      int np=++tot;l[np]=l[p]+1;
      for(;p&&!go[p][w];p=fa[p])go[p][w]=np;
      if(!p)fa[np]=1;
      else
    {
      int q=go[p][w];
      if(l[q]==l[p]+1)fa[np]=q; else fa[np]=cz(p,w);
    }
      return np;
    }
}
char ch[N2]; int Q;
int main()
{
  scanf("%d%d",&n,&Q);
  for(int i=1;i<=n;i++)
    {
      scanf("%s",ch);len[i]=strlen(ch);
      s[i]=(string)ch;
      for(int pr=1,j=0,lm=len[i];j)
    pr=ins(pr,ch[j]-'a'+1);
    }
  for(int i=1;i<=n;i++)
    for(int cr=1,j=0,lm=len[i];j)
      {
    cr=go[cr][s[i][j]-'a'+1];
    for(int p=cr;p>1&&vis[p]!=i;p=fa[p])
      ct[p]++,vis[p]=i;
      }
  while(Q--)
    {
      scanf("%s",ch);int lm=strlen(ch),cr=1;
      for(int j=0;j)
    cr=go[cr][ch[j]-'a'+1];
      printf("%d\n",ct[cr]);
    }
  return 0;
}