I Love Palindrome String

时间限制: 2 Sec 内存限制: 128 MB

题目描述

You are given a string S=s1s2..s|S| containing only lowercase English letters. For each integer i∈[1,|S|] , please output how many substrings slsl+1...srsatisfy the following conditions:
∙ r−l+1 equals to i.
∙ The substring slsl+1...sr is a palindrome string.
∙ slsl+1...s⌊(l+r)/2⌋ is a palindrome string too.
|S| denotes the length of string S.
A palindrome string is a sequence of characters which reads the same backward as forward, such as madam or racecar or abba.

输入

There are multiple test cases.
Each case starts with a line containing a string S(1≤|S|≤3×105) containing only lowercase English letters.
It is guaranteed that the sum of |S| in all test cases is no larger than 4×106.

输出

For each test case, output one line containing |S| integers. Any two adjacent integers are separated by a space.

样例输入

abababa

样例输出

7 0 0 0 3 0 0

题意：求有多少个字符串为回文串，且它的前一半也是回文串。
回文树+马拉车。先用回文树求出全部的本质不一样（就是长度不一样，或者长度一样内容不一样）的字符串，然后用马拉车快速判断该串是不是符合题意。

#include<bits/stdc++.h>

using namespace std;

//https://www.xuebuyuan.com/3184341.html

const int MAXN =  ;

const int N =  ;

int Palindromic_Length[MAXN*];

int ans[MAXN];

struct Palindromic_Tree

{

    int nxt[MAXN][],f[MAXN],cnt[MAXN],num[MAXN],len[MAXN],c[MAXN],last,n,L;

    int l[MAXN],r[MAXN];

    inline int newnode(int x)

    {

        for(register int i=; i<; ++i)

            nxt[L][i]=;

        cnt[L]=;

        len[L]=x;

        return L++;

    }

    void init()

    {

        L=;

        newnode();

        newnode(-);

        last=;

        n=;

        c[n]=-;

        f[]=;

    }

    inline int getf(int x)

    {

        while(c[n-len[x]-]!=c[n])

            x=f[x];

        return x;

    }

    inline void add(int x)

    {

        x-='a';

        c[++n]=x;

        int cur=getf(last);

        if(!nxt[cur][x])

        {

            int now=newnode(len[cur]+);

             l[now]=n-len[cur]-;

            r[now]=n;

            f[now]=nxt[getf(f[cur])][x];

            nxt[cur][x]=now;

        }

        ++cnt[last=nxt[cur][x]];

    }

    void count()

    {

        for(register int i=L-; i>=; --i)

            cnt[f[i]]+=cnt[i];

    }

    void getans()

    {

        count();

        for(int i=;i<L;i++)

        {

            int l1=l[i],r1=r[i];

            r1=(l1+r1)/;

            r1*=;

            l1*=;

            int mid=(r1+l1)/;

            if(mid-Palindromic_Length[mid]+<=(l1))

            {

                ans[len[i]]+=cnt[i];

            }

        }

    }

} PT;

string Manacher(string s)

{

    /*改造字符串*/

    string res="$#";

    for(int i=; i<s.size(); ++i)

    {

        res+=s[i];

        res+="#";

    }

    /*数组*/

    vector<int> P(res.size(),);

    int mi=,right=;   //mi为最大回文串对应的中心点，right为该回文串能达到的最右端的值

    int maxLen=,maxPoint=;    //maxLen为最大回文串的长度，maxPoint为记录中心点

    for(int i=; i<res.size(); ++i)

    {

        P[i]=right>i ?min(P[*mi-i],right-i):;     //关键句，文中对这句以详细讲解

        while(res[i+P[i]]==res[i-P[i]])

            ++P[i];

        if(right<i+P[i])    //超过之前的最右端，则改变中心点和对应的最右端

        {

            right=i+P[i];

            mi=i;

        }

        if(maxLen<P[i])     //更新最大回文串的长度，并记下此时的点

        {

            maxLen=P[i];

            maxPoint=i;

        }

        Palindromic_Length[i]=P[i]-;

       // printf("%d %d %c\n",i,P[i]-1,res[i]);

    }

    return s.substr((maxPoint-maxLen)/,maxLen-);

}

Palindromic_Tree tree;

int main()

{

    char s[MAXN];

    while(scanf("%s",s)==)

    {

        string a(s);

        tree.init();

        int len=strlen(s);

        for(int i=;i<len;i++)tree.add(s[i]),ans[i+]=;

        Manacher(a);

        tree.getans();

        for(int i=;i<=len;i++)printf("%d%c",ans[i],i==len ? '\n' : ' ');

    }

    //for(int i=0;i<a.size();i++)tree.add(a[i]);

    return ;

}

巴特西

I Love Palindrome String