최대 대칭 문자열 의 알고리즘

알고리즘 1:O(n^3)
문자열 의 대칭 여 부 를 밖에서 안 으로 판단 합 니 다.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;
}
/*
 *          ，      O(n^3)
 */
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;
}

알고리즘 2:O(n^2)
문자열 의 대칭 여 부 를 밖에서 안 으로 판단 합 니 다.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')
    {
    //      ，   aAa
    char* left = pChar - 1;
    char* right = pChar + 1;
    while(left >= pString && *right != '\0' && *left==*right)
    {
        left--;
        right++;
    }
    int newLength = right - left - 1;   //     *left!=*right
    if(newLength > symmetricalLength)
        symmetricalLength = newLength;
    //      ，   aAAa
    left = pChar;
    right = pChar + 1;
    while(left >= pString && *right != '\0' && *left==*right)
    {
        left--;
        right++;
    }
    newLength = right - left - 1;   //     *left!=*right
    if(newLength > symmetricalLength)
        symmetricalLength = newLength;
    pChar++;
    }
    return symmetricalLength;
}
int main()
{
    char* str = "google";
    int len = GetLongestSymmetricalLength(str);
    printf("%d", len);
    return 0;
}

알고리즘 3:manacher 알고리즘
 원본 문자열:abaab 새 문자열:\#a\#b\#a\#b\#이렇게 되면 원래 의 홀수 길이 의 답장 문자열 은 홀수 길이 이 고 짝수 길이 도'\#'를 중심 으로 하 는 홀수 답장 문자열 이 됩 니 다.다음은 알고리즘 의 중심 사상 입 니 다.보조 배열 P 로 모든 문 자 를 중심 으로 하 는 가장 긴 회 문 반지름,즉 P[i]기록 은 Str[i]문 자 를 중심 으로 하 는 가장 긴 회 문 꼬치 반지름 입 니 다.P[i]최소 1,이때 답장 문자열 은 Str[i]자체 입 니 다.우 리 는 상기 예 에 대해 P 배열 을 쓸 수 있 습 니 다.다음 과 같은 새 문자열 을 쓸 수 있 습 니 다.\#a\#a\#b\#P[]  :  1,2,1,4,1,2,1,2,1.우 리 는 P[i]-1 이 바로 Str[i]를 중심 으로 하 는 회 문 꼬치 의 길 이 를 증명 할 수 있다.증명:1.분명히 L=2*P[i]-1 은 새 꼬치 중 Str[i]를 중심 으로 가장 긴 회 문 꼬치 길이 입 니 다.2.Str[i]를 중심 으로 하 는 리 턴 문자열 은 반드시\#로 시작 하고 끝 납 니 다.예 를 들 어'\#b\#'또는'\#b\#a\#b\#'이기 때문에 L 에서 맨 앞 이나 마지막'\#'문 자 를 빼 면 원래 문자열 의 길이 의 두 배 입 니 다.즉,원래 문자열 의 길 이 는(L-1)/2 이 고 간단 한 P[i]-1 입 니 다.증 거 를 얻다.
주:잘 모 르 겠 어 요.

#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("%s
", 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;
}