CodeForces 17E Palisection(回文树)

E. Palisection

time limit per test

2 seconds

memory limit per test

128 megabytes

input

standard input

output

standard output

In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».

Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.

Let's look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:

• «b» — 1..1 • «bab» — 1..3 • «a» — 2..2 • «b» — 3..3 • «bb» — 3..4 • «b» — 4..4

Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:

1. 1..1 cross with 1..3 2. 1..3 cross with 2..2 3. 1..3 cross with 3..3 4. 1..3 cross with 3..4 5. 3..3 cross with 3..4 6. 3..4 cross with 4..4

Since it's very exhausting to perform all the described actions manually, Nick asked you to help him and write a program that can find out the amount of different subpalindrome pairs that cross. Two subpalindrome pairs are regarded as different if one of the pairs contains a subpalindrome that the other does not.

Input

The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from ato z).

Output

In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.

Examples

input

4
babb

output

6

input

2
aa

output

2

给你一个串让你求,所有相交的回文子串对的个数

我们可以利用回文树求出以s[i]为结尾的回文子串个数Ai,和以s[i]为开始的的回文串个数Bi

那么不相交的回文子串对就是Ai*sum{Bi+1,Bi+2,Bi+3....Bi+n} {i=1..n-1};

然后用总的回文串对数减去不相交的就是答案。

我们知道利用回文树可以求出以i为结尾的回文串个数,那么以i为开始的,只需要将字符串倒着插入就好了。

另外,这道题目的字符串的长度有2百万,回文树中的next[][]数组,将会内存超限,所以只能用邻接表代替矩阵了

为了对回文树更好的学习,在求所有回文子串和的时候我们可以用两种方式,具体看代码

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long int LL;
const int MAX=2*1e6;
const int mod=51123987;
int n;
char str[MAX+5];
int sum[MAX+5];
struct link //next的邻接表
{
    int u[MAX+5];int v[MAX+5];
    int next[MAX+5];int head[MAX+5];
    int tot;
    void clear()
    {
        memset(head,-1,sizeof(head));
        tot=0;
    }
    void clear(int x){head[x]=-1;}
    int get(int x,int y)
    {
        for(int i=head[x];i!=-1;i=next[i])
        {
            if(u[i]==y)
                return v[i];
        }
        return 0;
    }
    void insert(int x,int y,int z)
    {
        u[tot]=y;  v[tot]=z;
        next[tot]=head[x];
        head[x]=tot++;
    }

};
struct Tree
{
    //int next[MAX+5][26];
    int fail[MAX+5];//指向当前节点回文串中最长的后缀回文子串
    int cnt[MAX+5];//当前节点的回文串一共有多少个
    int num[MAX+5];//当前节点为结尾的回文子串的个数
    int len[MAX+5];//当前节点的回文串的长度
    int s[MAX+5];//字符串
    int last;//回文树最后一个节点
    int n;
    int p;//回文树当前有多少个节点
    link next;//邻接表,表示当前节点回文串在两端添加一个字符形成的另一个节点的回文串
    int new_node(int x)
    {
        //memset(next[p],0,sizeof(next[p]));
        cnt[p]=0;
        next.clear(p);
        num[p]=0;
        len[p]=x;
        return p++;
    }

    void init()
    {
        next.clear();
        p=0;
	new_node(0);
        new_node(-1);
        last=0;
        n=0;
        s[0]=-1;
        fail[0]=1;
    }

    int get_fail(int x)
    {
        while(s[n-len[x]-1]!=s[n])
            x=fail[x];
        return x;
    }

    int add(int x)
    {
        x-='a';
        s[++n]=x;
        int cur=get_fail(last);
        if(!(last=next.get(cur,x)))
        {
            int now=new_node(len[cur]+2);
	    fail[now]=next.get(get_fail(fail[cur]),x);
            next.insert(cur,x,now);
            num[now]=num[fail[now]]+1;
	    last=now;
        }
        cnt[last]++;
        return num[last];
    }
    LL Allsum()//求出所有回文子串的数目
    {
        LL ret=0;

        for(int i=p-1;i>0;i--)
        {
	    cnt[fail[i]]=(cnt[fail[i]]+cnt[i])%mod;

            ret=(ret+cnt[i])%mod;
        }
        return ret;
    }
}tree;
int main()
{
    scanf("%d",&n);
    scanf("%s",str);
    tree.init();
    sum[n]=0;
    for(int i=n-1;i>=0;i--)
        sum[i]=(sum[i+1]+tree.add(str[i]))%mod;
    tree.init();
    LL ans=0;LL res=0;LL res2=0;
    for(int i=0;i<=n-1;i++)
    {
        ans=(ans+(LL)tree.add(str[i])*sum[i+1])%mod;
        res2+=tree.num[tree.last];//同样也可以求所有回文子串的数目
    }
	res=tree.Allsum();
	//cout<<res<<" "<<res2<<endl;两个是相等的
    ans=(((LL)res*(res-1)/2%mod-ans)%mod+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.2K20
来自专栏腾讯社交用户体验设计

ISUX Xcube智能一键生成H5

51620
来自专栏钱塘大数据

中国互联网协会发布:《2018中国互联网发展报告》

在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

13750
来自专栏怀英的自我修炼

考研英语-1-导学

英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

12310
来自专栏微信公众号:小白课代表

不只是软件,在线也可以免费下载百度文库了。

不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

44830
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

18430
来自专栏腾讯高校合作

【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

16220
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

30740
来自专栏钱塘大数据

理工男图解零维到十维空间,烧脑已过度,受不了啦!

让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

35230
来自专栏前端桃园

知识体系解决迷茫的你

最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

22440

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励