I Love Palindrome String

2023-09-24 08:21:09

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 = 300005 ;
const int N = 26 ;

int Palindromic_Length[MAXN*2];
int ans[MAXN];

struct Palindromic_Tree
{
    int next[MAXN][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成
    int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
    int cnt[MAXN] ;
    int num[MAXN] ;
    int len[MAXN] ;//len[i]表示节点i表示的回文串的长度
    int S[MAXN] ;//存放添加的字符
    int last ;//指向上一个字符所在的节点，方便下一次add
    int n ;//字符数组指针
    int p ;//节点指针
    int l[MAXN],r[MAXN];


    int newnode ( int l )  //新建节点
    {
        for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
        cnt[p] = 0 ;
        num[p] = 0 ;
        len[p] = l ;
        return p ++ ;
    }

    void init ()  //初始化
    {
        p = 0 ;
        newnode (  0 ) ;
        newnode ( -1 ) ;
        last = 0 ;
        n = 0 ;
        S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
        fail[0] = 1 ;
    }

    int get_fail ( int x )  //和KMP一样，失配后找一个尽量最长的
    {
        while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
        return x ;
    }

    void add ( int c )
    {
        c -= 'a' ;
        S[++ n] = c ;
        int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置

        if ( !next[cur][c] )  //如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
        {
            // printf("%d %d\n",n-len[cur]-2,n-1);
            int now = newnode ( len[cur] + 2 ) ;//新建节点

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

            fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
            next[cur][c] = now ;
            num[now] = num[fail[now]] + 1 ;
        }
        last = next[cur][c] ;
        cnt[last] ++ ;
    }

    void count ()
    {
        for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
        //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
    }

    void getans()
    {
        count();
        for(int i=0;i<p;i++)
        {
            int l1=l[i],r1=r[i];
            r1=(l1+r1)/2;

            r1*=2;
            l1*=2;

            int mid=(r1+l1)/2;

            if(mid-Palindromic_Length[mid]+1<=(l1))
            {
                ans[len[i]]+=cnt[i];
            }
        }
    }

};


string Manacher(string s)
{
    /*改造字符串*/
    string res="$#";
    for(int i=0; i<s.size(); ++i)
    {
        res+=s[i];
        res+="#";
    }

    /*数组*/
    vector<int> P(res.size(),0);
    int mi=0,right=0;   //mi为最大回文串对应的中心点，right为该回文串能达到的最右端的值
    int maxLen=0,maxPoint=0;    //maxLen为最大回文串的长度，maxPoint为记录中心点

    for(int i=1; i<res.size(); ++i)
    {
        P[i]=right>i ?min(P[2*mi-i],right-i):1;     //关键句，文中对这句以详细讲解

        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]-1;

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

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

Palindromic_Tree tree;
int main()
{
    char s[MAXN];

    while(scanf("%s",s)==1)
    {
        string a(s);
        tree.init();

        int len=strlen(s);
        for(int i=0;i<len;i++)tree.add(s[i]),ans[i+1]=0;
        Manacher(a);
        tree.getans();
        for(int i=1;i<=len;i++)printf("%d%c",ans[i],i==len ? '\n' : ' ');
    }
    //for(int i=0;i<a.size();i++)tree.add(a[i]);
    return 0;

}

View Code

回文树参考博客：https://www.xuebuyuan.com/3184341.html

马拉车参考博客：https://www.cnblogs.com/love-yh/p/7072161.html

码农公寓