最大対称文字列のアルゴリズム

アルゴリズム1:O(n^3)
文字列が対称であるか否かを判断し,O(n)

 
  
#include  
  
#include  
   
  
/*
 *      ，             
 */
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  
  
#include  
   
  

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#a#b#このようにすると、元の奇数長回文列は奇数長であり、偶数長のものも'#'を中心とした奇数回文列となる.次にアルゴリズムの中心思想として,各文字を中心とした最長回文半径,すなわちP[i]を1つの補助配列Pで記録し,Str[i]文字を中心とした最長回文列半径を記録する.P[i]の最小値は1であり、このとき回文列はStr[i]そのものである.上記の例についてP配列を書くことができ、以下の新しい列:#a#b#a#a#b#P[]:1 2 1 4 1 2 5 1 1 2 1 P[i]-1がStr[i]を中心とした回文列の元の列の長さであることを証明することができる.証明:1、明らかにL=2*P[i]-1は新しい列の中でStr[i]を中心として最も長い文列の長さである.2、Str[i]を中心とした回文列は必ず#の先頭と末尾であり、例えば「#b#b#」や「#b#a#b#」であるため、Lから一番前または最後の「#」を減算する文字は元の列の長さの2倍であり、すなわち元の列の長さは(L-1)/2であり、簡略化されたP[i]-1である.証拠を得る.
よくわからないので、自分で直しました.

 
  
#include  
  
#include  
   
  
int GetLongestSymmetricalLength(char* pString)
{
    int length = strlen(pString);
    char* pNewString = malloc(2*length+2);
    int i;
    for(i=0; 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;
}