I Love Palindrome String

By Rom

I Love Palindrome String

Time limit: 2 Sec Memory limit: 128 MB

topic description

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.

< h4>Enter

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×10 6.

Output

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

Sample input

abababa

Sample output

7 0 0 0 3 0 0
 pre> 
 
The meaning of the question: Find how many strings are palindrome strings, and the first half of them are also palindrome strings. 
Palindrome tree + horse-drawn cart. First use the palindrome tree to find all the strings with different essences (that is, the length is different, or the length is the same, or the content is different), and then use a horse-drawn cart to quickly determine whether the string meets the meaning of the question. 


 Share picture  




#include

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 pointer, next pointer is similar to dictionary tree, the string pointed to is composed of the same character at both ends of the current string

 int fail[MAXN] ;//fail pointer, jump to the node pointed to by the fail pointer after mismatch

 int cnt[MAXN];

 int num[MAXN];

 int len[MAXN] ;//len[i] represents the length of the palindrome represented by node i

 int S[MAXN] ;//Store added characters

 int last ;//Point to the node where the previous character is located, convenient for the next add

 int n ;//Character array pointer

 int p ;//Node pointer

 int l[MAXN],r[MAXN];





 int newnode (int l) //New node

 {

 for (int i = 0; i 0;

 cnt[p] = 0;

 num[p] = 0;

 len[p] = l;

 return p ++;

}



 void init () //Initialization

 {

 p = 0;

 newnode (0 );

 newnode (-1 );

 last = 0;

 n = 0;

 S[n] = -1 ;//  Put a character that is not in the character set at the beginning to reduce special judgments

 fail[0] = 1;

}



 int get_fail (int x) //Like KMP, find the longest possible after mismatch

 {

 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) ;// Find the matching position of this palindrome from the previous palindrome



 if (!next[cur][c]) //< span style="color: #008000;">If this palindrome has not appeared before, it means that a new palindrome with a different nature has appeared

 {

 // printf("%d %d
",n -len[cur]-2,n-1);

 int now = newnode (len[cur] + 2) ;< span style="color: #008000;">//New node



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

 r[now]=n;



 fail[now] = next[get_fail (fail[cur] )][c] ;//Set up a fail pointer like AC automata, so that it can jump after mismatch

 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]] +=< span style="color: #000000;"> cnt[i];

 //The father accumulates the son’s cnt, because if it fails[v] =u, then u must be a sub-palindromic string of v! 

}



 void getans()

 {

 count();

 for(int i=0;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)

{

 /*Modify string*/

 string res="$#";

 for(int i=0; ii)

 {

 res+=s[i];

 res+="#";

}



 /*Array*/

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

 int mi=0,right=0; //mi is the largest palindrome The center point corresponding to the string, right is the rightmost value that the palindrome string can reach

 int maxLen=0,maxPoint=0; //maxLen is the length of the maximum palindrome string, maxPoint is the recording center point



 for(int i=1; ii)

 {

 P[i]=right>i ?min(P[2*mi-i],right-i):< span style="color: #800080;">1; //Key sentence, This sentence is explained in detail in the article



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

 ++P[i];



 if(right//< /span>Exceed the previous rightmost end, then change the center point and the corresponding rightmost end

 {

 right=i+P[i];

 mi=i;

}



 if(maxLen//Update the length of the largest palindrome and write down the point at this time

 {

 maxLen=P[i];

 maxPoint=i;

}

 Palindromic_Length[i]=P[i]-1;



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



}

 return s.substr((maxPoint-maxLen)/2 span>,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;i1] =0;

 Manacher(a);

 tree.getans();

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

}

 //for(int i=0;i

 return 0 ;



}




 View Code 


Palindrome tree reference blog: https://www. xuebuyuan.com/3184341.html


Horse-drawn cart reference blog: https://www.cnblogs.com/love-yh/p/7072161.html




 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: < br>? 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.


share picture  




#include

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 pointer, next pointer is similar to dictionary tree, the string pointed to is composed of the same character at both ends of the current string

 int fail[MAXN] ;//fail pointer, jump to the node pointed to by the fail pointer after mismatch

 int cnt[MAXN];

 int num[MAXN];

 int len[MAXN] ;//len[i] represents the length of the palindrome represented by node i

 int S[MAXN] ;//Store added characters

 int last ;//Point to the node where the previous character is located, convenient for the next add

 int n ;//Character array pointer

 int p ;//Node pointer

 int l[MAXN],r[MAXN];





 int newnode (int l) //New node

 {

 for (int i = 0; i 0;

 cnt[p] = 0;

 num[p] = 0;

 len[p] = l;

 return p ++;

}



 void init () //Initialization

 {

 p = 0;

 newnode (0 );

 newnode (-1 );

 last = 0;

 n = 0;

 S[n] = -1 ;//  Put a character that is not in the character set at the beginning to reduce special judgments

 fail[0] = 1;

}



 int get_fail (int x) //Like KMP, find the longest possible after mismatch

 {

 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) ;// Find the matching position of this palindrome from the previous palindrome



 if (!next[cur][c]) //< span style="color: #008000;">If this palindrome has not appeared before, it means that a new palindrome with a different nature has appeared

 {

 // printf("%d %d
",n -len[cur]-2,n-1);

 int now = newnode (len[cur] + 2) ;< span style="color: #008000;">//New node



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

 r[now]=n;



 fail[now] = next[get_fail (fail[cur] )][c] ;//Set up a fail pointer like AC automata, so that it can jump after mismatch

 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]] +=< span style="color: #000000;"> cnt[i];

 //The father accumulates the son’s cnt, because if it fails[v] =u, then u must be a sub-palindromic string of v! 

}



 void getans()

 {

 count();

 for(int i=0;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)

{

 /*Modify string*/

 string res="$#";

 for(int i=0; ii)

 {

 res+=s[i];

 res+="#";

}



 /*Array*/

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

 int mi=0,right=0; //mi is the largest palindrome The center point corresponding to the string, right is the rightmost value that the palindrome string can reach

 int maxLen=0,maxPoint=0; //maxLen is the length of the maximum palindrome string, maxPoint is the recording center point



 for(int i=1; ii)

 {

 P[i]=right>i ?min(P[2*mi-i],right-i):< span style="color: #800080;">1; //Key sentence, This sentence is explained in detail in the article



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

 ++P[i];



 if(right//< /span>Exceed the previous rightmost end, then change the center point and the corresponding rightmost end

 {

 right=i+P[i];

 mi=i;

}



 if(maxLen//Update the length of the largest palindrome and write down the point at this time

 {

 maxLen=P[i];

 maxPoint=i;

}

 Palindromic_Length[i]=P[i]-1;



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



}

 return s.substr((maxPoint-maxLen)/2 span>,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;i1]=0;

        Manacher(a);

        tree.getans();

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

}

    //for(int i=0;i

    return 0;



}




 View Code


#include

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-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)

 {

            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; ii)

 {

        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; ii)

 {

        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//超过之前的最右端，则改变中心点和对应的最右端

        {

            right=i+P[i];

            mi=i;

}



        if(maxLen//更新最大回文串的长度，并记下此时的点

        {

            maxLen=P[i];

            maxPoint=i;

}

        Palindromic_Length[i]=P[i]-1;



       // printf("%d %d %c
",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;i1]=0;

        Manacher(a);

        tree.getans();

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

}

    //for(int i=0;i

    return 0;



}
, ,

WordPress database error: [Table 'yf99682.wp_s6mz6tyggq_comments' doesn't exist]
SELECT SQL_CALC_FOUND_ROWS wp_s6mz6tyggq_comments.comment_ID FROM wp_s6mz6tyggq_comments WHERE ( comment_approved = '1' ) AND comment_post_ID = 3961 ORDER BY wp_s6mz6tyggq_comments.comment_date_gmt ASC, wp_s6mz6tyggq_comments.comment_ID ASC

Leave a Comment

Your email address will not be published.