题意

找如下子串的个数：

(l,r)是回文串，并且(l,(l+r)/2)也是回文串

思路

本来写了个回文树+dfs+hash，由于用了map所以T了

后来发现既然该子串和该子串的前半部分都是回文串，所以该子串的前半部分和后半部分是本质相同的！

于是这个log就去掉了

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-6;

const int mod = 1e9+7;

const int maxn = 8e5+100;

const int maxm = 2e6+100;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

const ull base = 201326611;

ull po[maxn],ha[maxn];

ull getHash(int l, int r){

    return ha[r]-ha[l-1]*po[r-l+1];

}

int ans[maxn];

int id[maxn];

struct pam{

    int nx[maxn][26],num[maxn],cnt[maxn],fail[maxn];

    int len[maxn],s[maxn],p,lst,n;

    int newNode(int x){

        mem(nx[p],0);

        cnt[p]=num[p]=0;

        len[p]=x;

        return p++;

    }

    void init(){

        p=0;newNode(0);newNode(-1);

        lst=0;n=0;s[0]=-1;fail[0]=1;

    }

    int getFail(int x){

        while(s[n-len[x]-1]!=s[n])x=fail[x];

        return x;

    }

    void add(int x){

        x-='a';

        s[++n]=x;

        int cur=getFail(lst);

        if(!(lst=nx[cur][x])){//产生新节点

            int now = newNode(len[cur]+2);

            fail[now]=nx[getFail(fail[cur])][x];

            nx[cur][x]=now;

            num[now]=num[fail[now]]+1;

            lst=now;

            id[now]=n;

        }

        cnt[lst]++;

    }

    void count(){

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

        for(int i = 2; i < p; i++){

            int l = id[i]-len[i]+1;

            int r = id[i];

            int mid = (l+r)>>1;

            if(len[i]%2==1&&getHash(l,mid)==getHash(mid,r))ans[len[i]]+=cnt[i];

            if(len[i]%2==0&&getHash(l,mid)==getHash(mid+1,r))ans[len[i]]+=cnt[i];

        }

    }

}pam;

int n;

char s[maxn];

int main(){

    po[0]=1;

    for(int i = 1; i <= 3e5+10; i++){

        po[i]=po[i-1]*base;

    }

    while(~scanf("%s",s+1)){

        n=strlen(s+1);

        pam.init();

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

            ans[i]=0;

            ha[i]=ha[i-1]*base+s[i]-'a'+1;

            pam.add(s[i]);

        }pam.count();

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

            printf("%d", ans[i]);

            if(i!=n)printf(" ");

        }printf("\n");

    }

    return 0;

}

/*

 */

巴特西

HDU 6599 I Love Palindrome String (回文树+hash)

题意

思路

代码

最新文章

热门文章