BZOJ 4460 [Jsoi2013]广告计划 ——Bitset 后缀自动机

#include 
using namespace std;
  
#define maxn 100005
int fa[maxn],go[maxn][26],last,cnt,l[maxn],v[maxn],q[maxn];
char s[maxn];
bitset  bit[maxn],Nothing,dp[2][2];
  
void init()
{
    last=cnt=1;
}
  
void add(int x,int pos)
{
    int p=last,q;
    if ((q=go[p][x])){
        if (l[q]==l[p]+1) last=q;
        else{
            int nq=++cnt;
            l[nq]=l[p]+1;
            memcpy(go[nq],go[q],sizeof go[q]);
            fa[nq]=fa[q];
            fa[q]=nq;
            for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq;
            last=nq;
        }
    }
    else{
        int np=++cnt; l[np]=l[p]+1;
        for (;p&&!go[p][x];p=fa[p]) go[p][x]=np;
        if (!p) fa[np]=1;
        else{
            q=go[p][x];
            if (l[q]==l[p]+1) fa[np]=q;
            else {
                int nq=++cnt;
                l[nq]=l[p]+1;
                memcpy(go[nq],go[q],sizeof go[q]);
                fa[nq]=fa[q];
                fa[q]=fa[np]=nq;
                for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq;
            }
        }
        last=np;
    }
    bit[last][pos]=1;
}
  
void insert()
{
    last=1;
    scanf("%s",s+1);
    int Len=strlen(s+1);
    for (int i=1;i=1;--i) q[v[l[i]]--]=i;
    for (int i=cnt;i>=1;--i)
        bit[fa[q[i]]]|=bit[q[i]];
}
  
int n,m,Len;
char t[maxn];
  
  
bool test(int x)
{
    int now=1,pre=0;
    dp[now][0].reset();
    dp[now][1].reset();
    dp[now][0].set();
    int all=(Len+x-1)/x;
    for (int i=1;i Match=bit[pos];
            if (tmp Test;
      
    Radix();
      
    Nothing.reset();
    scanf("%s",t+1);
    Len=strlen(t+1);
    for (int i=1;i