Solemnly declare: This article is reprinted. See the following link for the original article#

Link: Manacher algorithm

Since palindromes are divided into even palindromes (such as bccb) and odd palindromes (such as bcacb), and it is cumbersome to deal with odd and even problems, here we use a technique to insert a character between characters (provided that this character does not appear in the string). For example: s="abbahopxpo", converted to s_ New= "$\a\b\b\a\h\o\p\x\p\o\x" (the character $here is just to prevent cross-border, which will be explained in the following code). In this way, there is an even palindrome abba and an odd palindrome opxpo in s, which are converted to \a\b\b\a\and \o\p\x\p\o\.

Define an auxiliary array int p[], p[i] expressed in S_ Radius of the longest palindrome centered on new[i].

P.s:_ Here, s is the original input string, and snew is the changed string_

Here comes the point!!!

Set two variables, mx and id.

MX stands for S_ The rightmost boundary of the longest palindrome centered on new[id], that is, mx=id+p[id].

Suppose we now find p[i], that is, with s_new[i] is the longest palindrome radius of the center. If i<mx, as shown in the above figure, then:

  if (i < mx)  
      p[i] = min(p[2 * id - i], mx - i);

2 * id -i is actually equal to j, p[j] is expressed as s_ The longest palindrome radius centered on new[j], as shown in the figure above, because I and j are symmetrical about ID, we use p[j] to speed up the search.

Here is the source code:

    #include<iostream>  
    #include<string.h>
    #include<algorithm>  
    using namespace std;
    char s[1000];
    char s_new[2000];
    int p[2000];
    int Init()
    {
        int len = strlen(s);
        s_new[0] = '$';
        s_new[1] = '#';
        int j = 2;
        for (int i = 0; i < len; i++)
            {
            s_new[j++] = s[i];
            s_new[j++] = '#';
        }
        s_new[j] = '\0';  //Don't forget  
        return j;  //Return s_ Length of new  
    }
    int Manacher()
    {
        int len = Init();  //Get the new string length and complete the transfer to s_new conversion  
        int maxLen = -1;   //Maximum palindrome length  
        int id;
        int mx = 0;
        for (int i = 1; i < len; i++)
        {
            if (i < mx)
                p[i] = min(p[2 * id - i], mx - i);  //It is necessary to understand the meaning of the above figure, mx and 2*id-i
            else
                p[i] = 1;
            while (s_new[i - p[i]] == s_new[i + p[i]])  //No boundary judgment is required because there is' $'on the left and' \0'on the right  
                p[i]++;
            if (mx < i + p[i])  //At each step i, we have to compare with mx. We want mx to be as far as possible, so that we can have a better chance to execute if (i < mx) and improve efficiency  
            {
                id = i;
                mx = i + p[i];
            }
                maxLen = max(maxLen, p[i] - 1);
        }
        return maxLen;
    }
    int main()
    {
           while (printf("Please enter a string:\n"))
        {
            scanf("%s", s);
            printf("The longest palindrome length is %d\n\n", Manacher());
        }
        return 0;
    }

The following is my code for this question:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=11000005;
char origin[N],final[2*N];
int help[2*N];
int ct,mr;
int init();
int main()
{
    ct=1; mr=1;
    int ans=-1;
    int lenf=init();
    for(int i=1;i<lenf;++i)
    {
        if(i<mr)
        help[i]=min(mr-i,help[2*ct-i]);
        else
        help[i]=1;
        int num=0;
        while(final[i-help[i]]==final[i+help[i]])
            help[i]++;
        if(i+help[i]>mr)//☣
        {
            mr=i+help[i];
            ct=i;
        }
    }
    for(int i=1;i<lenf;++i)
    {
        if(ans<help[i])
        ans=help[i];
    }
    printf("%d",ans-1);
    return 0;
}
int init()
{
    scanf("%s",origin);
    int leno=strlen(origin);
       final[0] = '$';
    final[1] = '#';
    int j = 2;
    for (int i = 0; i < leno; i++)
    {
        final[j++] = origin[i];
        final[j++] = '#';
    }
    final[j]='^';
    return j;
}