算法一：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 != '')

{

//奇数长度对称， 如 aAa

char* left = pChar - 1;

char* right = pChar + 1;

while(left >= pString && *right != '' && *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 != '' && *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记录以每个字符为中心的最长回文半径，也就是P[i]记录以Str[i]字符为中心的最长回文串半径。P[i]最小为1，此时回文串为Str[i]本身。

我们可以对上述例子写出其P数组，如下

新串： # a # b # a # a # b #

P[] : 1 2 1 4 1 2 5 2 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减去最前或者最后的‘#'字符就是原串中长度的二倍，即原串长度为(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) = '';

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!=''&& *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;

}