求字符串中的最长回文子串

方法一（暴力法）：

#include <stdio.h>
#include <string.h>
bool Palindrome(const char *str, int start, int end)  
{  
	for(int i = start, j = end; i < j; i++, j--)  
	{  
		if(str[i] != str[j])  
		{  
			return false;  
		}  

	}  
	return true;  
}
int main()
{
	char *str = "adaiziguizhongrenergnohziugiziada";
	int i, j, n, maxLength = 0, start, end;
	n = strlen(str);
	for (i = 0; i < n; ++i)
	{
		for (j = n-1; j >= i; --j)
		{
			if (Palindrome(str, i, j))
			{
				if ((j - i) > maxLength)
				{
					maxLength = j - i;
					start = i; 
					end = j;
				}				
			}
			else continue;
		}
	}
	for (i = start; i <= end; i++)
	{
		printf("%c",str[i]);
	}
	printf("\n%d\n", maxLength);
	return 0;
}

找出字符串中所有的回文子串,设定P[i][j]:

为true时，表示str[i...j]为回文；

为false时，表示str[i...j]不是回文。

则，当

i == j 时，表示P[i][j] = true;

j = i+ 1时，P[i][j] = str[i] == str[j];

其他，p[i][j] = P[i+1][j-1] && (str[i] == str[j])

根据其状态转移的方程，P[i][j]所代表的的字符串，长度从1开始变化，逐渐到整个字符串，是这样一个构建过程，所以外层循环应该是要所判断的字符串的长度，基本代码如下：

#include <stdio.h>
#include <string.h>
void isPalin(char *str)
{
	int n = strlen(str);
	bool P[n][n];
	int i, j, L;  //L表示字符串的长度
	//长度为1的都是回文
	for (i = 0; i < n; ++i)
	{
		P[i][i] = true;
	}
	//长度可能从2开始
	for (L = 2; L <= n; L++)
	{
		for (i = 0; i < n-L+1; i++)
		{
			j = i+L-1;	//设置结束的位置
			if (L == 2)		//长度为2的情况，递归出口
				P[i][i] = (str[i] == str[j]);
			else
				P[i][j] = (str[i] ==  str[j]) && P[i+1][j-1];
		}
	}
	return;
}