Maximum symmetric string algorithm

Algorithm 1: O(n^3)

To determine if the string is symmetric from the outside to the inside, O(n)

#include <stdio.h>
#include <string.h>

int IsSymmetrical(char* pBegin, char* pEnd)
{
    if(pBegin == NULL || pEnd == NULL || pBegin > pEnd)
    return 0;
    while(pBegin < pEnd)
    {
    if(*pBegin != *pEnd)
        return 0;
    pBegin++;
    pEnd--;
    }
    return 1;
}

int GetLongestSymmetricalLength(char* pString)
{
    if(pString == NULL)
    return 0;
    int symmetricalLength = 1;
    char* pFirst = pString;
    int length = strlen(pString);
    while(pFirst < &pString[length-1])
    {
    char* pLast = pFirst + 1;
    while(pLast <= &pString[length-1])
    {
        if(IsSymmetrical(pFirst, pLast))
        {
        int newLength = pLast - pFirst + 1;
        if(newLength > symmetricalLength)
            symmetricalLength = newLength;
        }
        pLast++;
    }
    pFirst++;
    }
    return symmetricalLength;
}
int main()
{
    char* str = "google";
    int len = GetLongestSymmetricalLength(str);
    printf("%d", len);
    return 0;
}

To determine if the string is symmetric is from the outside to the inside, O(1).

#include <stdio.h>
#include <string.h>

int GetLongestSymmetricalLength(char* pString)
{
    if(pString == NULL)
    return 0;
    int symmetricalLength = 1;
    char* pChar = pString;
    while(*pChar != '0')
    {
    //Odd length symmetry, like aAa
    char* left = pChar - 1;
    char* right = pChar + 1;
    while(left >= pString && *right != '0' && *left==*right)
    {
        left--;
        right++;
    }
    int newLength = right - left - 1;   //The exit loop is *left! = * right
    if(newLength > symmetricalLength)
        symmetricalLength = newLength;
    //Even length symmetry, like aAAa
    left = pChar;
    right = pChar + 1;
    while(left >= pString && *right != '0' && *left==*right)
    {
        left--;
        right++;
    }
    newLength = right - left - 1;   //The exit loop is *left! = * right
    if(newLength > symmetricalLength)
        symmetricalLength = newLength;
    pChar++;
    }
    return symmetricalLength;
}
int main()
{
    char* str = "google";
    int len = GetLongestSymmetricalLength(str);
    printf("%d", len);
    return 0;
}

Algorithm 3: manacher algorithm

  The original string: abaab
The new series: # # b# # # b#
As a result, the original odd length palindrome string is still an odd length, and the even length palindrome string is now an odd length palindrome string centered on '#'.
Next is the central idea of the algorithm, using an auxiliary array P to record the longest palindrome radius centered on each character, which is P[I] to record the longest palindrome radius centered on the Str[I] character. P[I] is at least 1, when the palindrome string is Str[I] itself.
We can write the P array for the above example, as follows
New string: # a # b # a # a # b #
P []   :   1, 2, 1, 4, 1, 2, 5, 2, 1, 2, 1
We can prove that P[I]-1 is the length of the palindrome string centered on Str[I] in the original string.
Proof:
1. Obviously, L=2*P[I]-1 is the longest palindrome string length centered on Str[I] in the new string.
2. Palindromes centered on Str[I] must start and end with #, such as "#b#b#" or "#b#a#b#", so L minus the first or last '#' character is twice the length of the original string, that is, the original string length is (l-1)/2, and the simplified P[I]-1. Have to pass.

Note: not very understand, oneself changed

#include <stdio.h>
#include <string.h>
int GetLongestSymmetricalLength(char* pString)
{
    int length = strlen(pString);
    char* pNewString = malloc(2*length+2);
    int i;
    for(i=0; i<length; i++)
    {
    *(pNewString+i*2) = '#';
    *(pNewString+i*2+1) = *(pString+i);
    }
    *(pNewString+2*length) = '#';
    *(pNewString+2*length+1) = '0';
    printf("%sn", pNewString);
    int maxLength = 1;
    char* pChar;
    for(i=0; i<2*length+2; i++)
    {
    int newLength = 1;
    pChar = pNewString + i;
    char* left = pChar-1;
    char* right = pChar+1;
    while(left>=pNewString && *right!='0'&& *left==*right)
    {
        left--;
        right++;
        newLength++;
    }
    if(newLength > maxLength)
        maxLength = newLength;
    }
    return maxLength-1;
}
int main()
{
    char* str = "google";
    int len = GetLongestSymmetricalLength(str);
    printf("%d", len);
    return 0;
}