最大對(duì)稱字符串的算法

更新時(shí)間：2013年03月06日 15:43:03 作者：

題目：輸入一個(gè)字符串，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度。比如輸入字符串“google”，由于該字符串里最長(zhǎng)的對(duì)稱子字符串是“goog”，因此輸出4。

算法一：O(n^3)

判斷字串是否對(duì)稱是從外到里， O(n)

復(fù)制代碼代碼如下:

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

/*
*判斷起始指針，到結(jié)束指針的字符串是否對(duì)稱
*/
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;
}

/*
*查找最大對(duì)稱字串長(zhǎng)度，時(shí)間復(fù)雜度是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)

判斷字串是否對(duì)稱是從外到里， O(1)

復(fù)制代碼代碼如下:

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

int GetLongestSymmetricalLength(char* pString)
{
    if(pString == NULL)
    return 0;
    int symmetricalLength = 1;

    char* pChar = pString;
    while(*pChar != '\0')
    {
    //奇數(shù)長(zhǎng)度對(duì)稱，如 aAa
    char* left = pChar - 1;
    char* right = pChar + 1;
    while(left >= pString && *right != '\0' && *left==*right)
    {
        left--;
        right++;
    }
    int newLength = right - left - 1;   //退出循環(huán)是*left!=*right
    if(newLength > symmetricalLength)
        symmetricalLength = newLength;

    //偶數(shù)長(zhǎng)度對(duì)稱，如 aAAa
    left = pChar;
    right = pChar + 1;
    while(left >= pString && *right != '\0' && *left==*right)
    {
        left--;
        right++;
    }
    newLength = right - left - 1;   //退出循環(huán)是*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#a#b#
這樣一來(lái)，原來(lái)的奇數(shù)長(zhǎng)度回文串還是奇數(shù)長(zhǎng)度，偶數(shù)長(zhǎng)度的也變成以‘#'為中心的奇數(shù)回文串了。
接下來(lái)就是算法的中心思想，用一個(gè)輔助數(shù)組P記錄以每個(gè)字符為中心的最長(zhǎng)回文半徑，也就是P[i]記錄以Str[i]字符為中心的最長(zhǎng)回文串半徑。P[i]最小為1，此時(shí)回文串為Str[i]本身。
我們可以對(duì)上述例子寫(xiě)出其P數(shù)組，如下
新串： # a # b # a # a # b #
P[] : 1 2 1 4 1 2 5 2 1 2 1
我們可以證明P[i]-1就是以Str[i]為中心的回文串在原串當(dāng)中的長(zhǎng)度。
證明：
1、顯然L=2*P[i]-1即為新串中以Str[i]為中心最長(zhǎng)回文串長(zhǎng)度。
2、以Str[i]為中心的回文串一定是以#開(kāi)頭和結(jié)尾的，例如“#b#b#”或“#b#a#b#”所以L減去最前或者最后的‘#'字符就是原串中長(zhǎng)度的二倍，即原串長(zhǎng)度為(L-1)/2，化簡(jiǎn)的P[i]-1。得證。

注: 不是很懂，自己改了

復(fù)制代碼代碼如下:

#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\n", 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;
    }