bzoj4480: [Jsoi2013]快乐的jyy

【问题描述】

给定两个字符串A和B，表示JYY的两个朋友的名字。我们用A(i,j)表示A

字符串中从第i个字母到第j个字母所组成的子串。同样的，我们也可以定义B(x,y)。

JYY发现两个朋友关系的紧密程度，等于同时满足如下条件的四元组(i,j,x,y)

的个数：

1:1<=i<=j<=|A|

2:1<=x<=y<=|B|

3:A(i,j)=B(x,y)

4:A(i,j)是回文串

这里表示字符串A的长度。

JYY希望你帮助他计算出这两个朋友之间关系的紧密程度。

建两个串的回文树，算出每个本质不同的回文串在两个串中出现次数，乘起来相加。

#include<bits/stdc++.h>

typedef long long i64;

const int N=1e5+;

char s1[],s2[];

int nx[N][],fa[N],l[N],t[N][],pv=,ptr=;

int gf(int w,char*s,int i){

    while(s[i]!=s[i--l[w]])w=fa[w];

    return w;

}

void ins(char*s,int x){

    int c=s[x]-'A',p=gf(pv,s,x);

    if(!nx[p][c]){

        int np=nx[p][c]=++ptr;

        l[np]=l[p]+;

        fa[np]=p==?:gf(fa[p],s,x)[nx][c];

    }

    pv=nx[p][c];

    ++t[pv][s==s2];

}

int main(){

    l[]=-;

    fa[]=fa[]=;

    scanf("%s%s",s1+,s2+);

    s1[]=s2[]=-;

    for(int i=;s1[i];++i)ins(s1,i);

    pv=;

    for(int i=;s2[i];++i)ins(s2,i);

    i64 ans=;

    for(int w=ptr;w>;--w){

        int f=fa[w];

        for(int d=;d<;++d)t[f][d]+=t[w][d];

        ans+=i64(t[w][])*t[w][];

    }

    printf("%llu\n",ans);

    return ;

}

巴特西

bzoj4480: [Jsoi2013]快乐的jyy

【问题描述】

最新文章

热门文章