hiho1602本质不同的回文子串的数量

给定一个字符串S，请统计S的所有子串中，有多少个本质不同的回文字符串？

注意如果两个位置不同的子串满足长度相同且对应字符也都相同，则认为这两个子串本质上是相同的。

Input

一个只包含小写字母的字符串S。

对于30%的数据，S长度不超过100。

对于60%的数据，S长度不超过1000。

对于100%的数据，S长度不超过800000。

Output

回文子串的数量

Sample Input

abbab

Sample Output

5

马拉车算法+bkrdhash：

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<map>

using namespace std;

#define ULL unsigned long long

const int maxn=+;

ULL P = ;

ULL sqr[maxn/],has[maxn/],V[maxn];

int Laxt[maxn],Next[maxn],cnt=;

const int MOD = ;

bool _insert(ULL Now)

{

       int u=Now%MOD;

       for(int i=Laxt[u];i;i=Next[i]){

        if(V[i]==Now) return true;

       }

       Next[++cnt]=Laxt[u];

       Laxt[u]=cnt;

       V[cnt]=Now;

       return false;

}

int ans=;void _hash(int x,int y){

    ULL Now=has[y]-has[x-]*sqr[y-x+];

    if(!_insert(Now)) ++ans;

}

void _malacher()

{

    int R=,Mid=,Len;

    char c[maxn];

    scanf("%s",c+);

    Len=strlen(c+);

    sqr[]=;

    for(int i=;i<=Len;i++){

        sqr[i]=sqr[i-]*P;

        has[i]=has[i-]*P+c[i];

    }

    int r[maxn];

     for(int i=;i<=Len;++i) {

        _hash(i,i);

        if(R>i) r[i]=min(r[*Mid-i],R-i);

        while(i+r[i]+<=Len&&c[i+r[i]+]==c[i-r[i]-]){

            _hash(i-r[i]-,i+r[i]+);

            r[i]++;

        }

        if(i+r[i]>R) {

            R=i+r[i];

            Mid=i;

        }

    }

    cnt=;Mid=;R=;

    memset(Laxt,,sizeof(Laxt));

    memset(r,,sizeof(r));

    for(int i=;i<=Len;++i) {

        if(R>i) r[i]=min(r[*Mid-i],R-i+);

        while(i+r[i]<=Len&&c[i+r[i]]==c[i-r[i]-]) {

            _hash(i-r[i]-,i+r[i]);

            ++r[i];

        }

        if(i+r[i]->R) {

            R=i+r[i]-;

            Mid=i;

        }

    }

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

}

int main()

{

    _malacher();

    return ;

}