Hihocoder #1602 : 本质不同的回文子串的数量 manacher + BKDRhash

#1602 : 本质不同的回文子串的数量

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

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

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

输入

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

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

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

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

输出

回文子串的数量

样例输入

abbab

样例输出

5

题解：

　　跑manacher的时候 hash标记即可

#include <bits/stdc++.h>

inline long long read(){long long x=,f=;char ch=getchar();while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}return x*f;}

using namespace std;

const long long INF = 1e14;

const int N = 1e6 + ;

unsigned long long P = 10000019ULL;

unsigned long long sqr[N],has[N];

//BKDRHash，最优的字符串hash算法。hash一开始是等于0的

const int seed = ; // 31 131 1313 13131 131313 etc..

const int maxn = +;

char str[maxn];

unsigned long long sumHash[maxn]; //前缀hash值

const int MOD = ;

struct StringHash

{

    int first[MOD+],num;

    unsigned long long EdgeNum[maxn]; // 表明第i条边放的数字(就是sumHash那个数字)

    int next[maxn],close[maxn]; //close[i]表示与第i条边所放权值相同的开始的最大位置

    //就比如baba，现在枚举长度是2，开始的时候ba，close[1] = 1;表明"ba"开始最大位置是从1开始

    //然后枚举到下一个ba的时候，close[1]就要变成3了，开始位置从3开始了

    void init ()

    {

        num = ; memset (first,,sizeof first);

        return ;

    }

    int insert (unsigned long long val,int id) //id是用来改变close[]的

    {

        int u = val % MOD;

        for (int i = first[u]; i ; i = next[i]) //存在边不代表出现过，出现过要用val判断，val才是唯一的，边还是压缩后(%MOD)的呢

        {

            if (val == EdgeNum[i]) //出现过了

            {

                int t = close[i]; close[i] = id;//更新最大位置

                return t;

            }

        }

        ++num; //没出现过的话，就加入图吧

        EdgeNum[num] = val; // 这个才是精确的

        close[num] = id;

        next[num] = first[u];

        first[u] = num;

        return ;//没出现过

    }

}H;

char a[N];

int ans = ;

map<unsigned long long, int> mp;

void gao(int i,int j) {

    unsigned long long now = has[j] - has[i-] * sqr[j-i+];

    if(!H.insert(now,)) ++ans,mp[now]++;

}

int r[N];

int main() {

    scanf("%s",a+);

    int n = strlen(a+);

    sqr[] = ;for(int i = ; i <= n; ++i) sqr[i] = sqr[i-] * P;

    for(int i = ; i <= n; ++i) has[i] = has[i-] * P + a[i];

    int x = , p = ;

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

        int j = ;

        gao(i,i);

        if(p > i) j = min(r[*x-i],p-i);

        while(i + j +  <= n&& a[i+j+] == a[i-j-])

        {

            gao(i-j-,i+j+);

            j++;

        }

        r[i] = j;

        if(i+j > p) {

            p = i + j;

            x = i;

        }

    }

    H.init();

    x = ,p = ;

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

        int j = ;

        if(p > i) j = min(r[*x-i],p-i+);

        while(i+j<=n && a[i+j] == a[i-j-]) {

            gao(i-j-,i+j);

            ++j;

        }

        r[i] = j;

        if(i+j- > p) {

            p = i+j-;

            x = i;

        }

    }

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

    return ;

}