51Nod 1600 Simple KMP 解题报告

51Nod 1600 Simple KMP

对于一个字符串\(|S|\)，我们定义\(fail[i]\)，表示最大的\(x\)使得\(S[1..x]=S[i-x+1..i]\)，满足\((x<i)\)

显然对于一个字符串，如果我们将每个\(0\le i\le |S|\)看成一个结点，除了\(i=0\)以外\(i\)向\(fail[i]\)连边，这是一颗树的形状，根是\(0\)

我们定义这棵树是\(G(S)\)，设\(f(S)\)是\(G(S)\)中除了\(0\)号点以外所有点的深度之和，其中\(0\)号点的深度为\(-1\)

定义\(key(S)\)等于\(S\)的所有非空子串\(S'\)的\(f(S')\)之和

给定一个字符串\(S\)，现在你要实现以下几种操作：

1.在\(S\)最后面加一个字符

2.询问\(key(S)\bmod 10^9+7\)

发现连的是KMP的fail边，然而这个并没有什么用处，考虑某个长\(n\)的串\(S\)的\(key(S)\)实际是什么

\[key(S)=\sum_{i=1}^n\sum_{j=i+1}^n(\sum_{l=i}^j\sum_{k=1}^{l-i}[S[i,i+k-1]=S[l-k+1,l]])
\]

前两个合式枚举子串，第三个枚举节点，第四个计算深度。

设

\[F(S)=\sum_{i=1}^n\sum_{k=1}^{n-i}[S[i,i+k-1]=S[n-k+1,n]]
\]

实际上计算的是钦定末尾位置，算前面的贡献。

可以得到

\[key(S)=\sum_{i=1}^n\sum_{j=1}^iF(S[1,j])
\]

然后对每个串，钦定每个可以成为末尾位置的\(j\)，求和一下就成了。

如果算出了\(F[1,i]\)，显然可以算出\(key\)

相等子串个数，考虑SAM

对于某个点\(i\)，当被加入SAM的时候，对\(par\)树上的到根的链上的每个点都存在相等的串的匹配，考虑计算这条链的贡献。

链上的一个点的贡献可以被描述为\(cnt*le\)，即在\([1,i-1]\)中出现的次数和这个点\(endpos\)所代表的集合的串长个数（就是\(len[x]-len[par[x]]\)）

计算完贡献后，我们需要对这些点的\(cnt\)进行区间加\(1\)

直接用LCT或者树剖在最后离线维护即可。

Code:

#include <cstdio>

#include <cstring>

const int N=4e5+10;

const int mod=1e9+7;

inline void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}

#define mul(x,y) (1ll*(x)*(y)%mod)

int n;

char s[N];

int len[N],par[N],tr[N][26],pos[N],tot=1,las=1;

void extend(int c)

{

    int now=++tot,p=las;

    len[now]=len[p]+1;

    while(p&&!tr[p][c]) tr[p][c]=now,p=par[p];

    if(!p) par[now]=1;

    else

    {

        int x=tr[p][c];

        if(len[x]==len[p]+1) par[now]=x;

        else

        {

            int y=++tot;

            len[y]=len[p]+1;

            par[y]=par[x];

            memcpy(tr[y],tr[x],sizeof tr[y]);

            while(p&&tr[p][c]==x) tr[p][c]=y,p=par[p];

            par[x]=par[now]=y;

        }

    }

    las=now;

}

int ch[N][2],L[N],R[N],tag[N],sum[N],dat[N],lp[N],rp[N];

#define ls ch[now][0]

#define rs ch[now][1]

#define fa par[now]

bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;}

int identity(int now){return ch[fa][1]==now;}

void connect(int f,int now,int typ){ch[fa=f][typ]=now;}

void updata(int now)

{

    sum[now]=0;

    add(sum[now],sum[ls]);

    add(sum[now],dat[now]);

    add(sum[now],sum[rs]);

    L[now]=lp[now];

    if(ls) L[now]=L[ls];

    R[now]=rp[now];

    if(rs) R[now]=R[rs];

}

void Rotate(int now)

{

    int p=fa,typ=identity(now);

    connect(p,ch[now][typ^1],typ);

    if(isroot(p)) connect(par[p],now,identity(p));

    else fa=par[p];

    connect(now,p,typ^1);

    updata(p),updata(now);

}

void upt(int now,int d)

{

    add(tag[now],d);

    add(dat[now],mul(d,rp[now]-lp[now]));

    add(sum[now],mul(d,R[now]-L[now]));

}

void pushdown(int now)

{

    if(tag[now])

    {

        if(ls) upt(ls,tag[now]);

        if(rs) upt(rs,tag[now]);

        tag[now]=0;

    }

}

int sta[N],ct;

void splay(int now)

{

    while(isroot(now)) sta[++ct]=now,now=fa;

    sta[++ct]=now;

    while(ct) pushdown(sta[ct--]);

    now=sta[1];

    for(;isroot(now);Rotate(now))

        if(isroot(fa))

            Rotate(identity(now)^identity(fa)?now:fa);

}

void access(int now)

{

    for(int las=0;now;las=now,now=fa)

        splay(now),rs=las,updata(now);

}

int qry(int now)

{

    access(now),splay(now);

    return sum[now];

}

void modi(int now)

{

    access(now),splay(now);

    upt(now,1);

}

int main()

{

    scanf("%d%s",&n,s+1);

    for(int i=1;i<=n;i++) extend(s[i]-'a'),pos[i]=las;

    //for(int i=2;i<=tot;i++) printf("%d %d\n",par[i],i);

    //for(int i=1;i<=n;i++) printf("%d ",pos[i]);puts("");

    int ans=0,yuu=0;

    for(int i=1;i<=tot;i++)

        lp[i]=L[i]=len[par[i]],rp[i]=R[i]=len[i];

    for(int i=1;i<=n;i++)

    {

        add(ans,qry(par[pos[i]]));

        modi(pos[i]);

        add(yuu,ans);

        printf("%d\n",yuu);

    }

    return 0;

}

2019.5.3

巴特西

51Nod 1600 Simple KMP 解题报告

51Nod 1600 Simple KMP

最新文章

热门文章