最长回文子串之DP做法

缘起

求最长回文子串之DP做法, 虽然实际上没什么卵用（依旧O(N^2)复杂度），但是知道一下还是很有必要的.

分析

dp的模型是,用二维bool数组isPalindrome,其中isPalindrome[i][j]表示str[i]到str[j]是不是回文. 那么很显然isPalindrome[i][j]=isPalindrome[i+1][j-1]&&str[i]==str[j],也就是左右各宽一格的区间是不是回文当且仅当原区间是回文并且左右各宽出来的那一格为相等字符
这就是dp模型，比较简单，接着我们就要考虑isPalindrome的初始化.显然isPalindrome[i][i]=true. 且是奇数长度的回文. 而如果只有这个初始值的话,我们只能得到奇数长度的回文,所以还必须初始化偶数长度的回文的始祖——长度为2的回文,有了这两个初始化，剩下的就是填表了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include "stdafx.h"
#include <string.h>
#include <stdio.h>
#define LOCAL

char s[105];
int n, ans;
bool dp[105][105]; // dp[i][j], i<=j 表示s[i,..,j]是否是回文

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%s", s))
	{
		memset(dp, 0, sizeof(dp));
		ans = 0;
		n = strlen(s);
		for (int i = 0; i<n; i++)
		{
			dp[i][i] = true;
		}
		for (int i = 0;i<n-1;i++)
		{
			if (s[i]==s[i+1])
			{
				dp[i][i+1] = true;
			}
		} // dp初始化
		for (int len = 3;len<=n; len++) // len是考察的字符串的长度
		{
			for (int i = 0,j;i<n; i++) // 考察 s[i,...,i+len-1]是否是回文
			{
				j = i+len-1;
				dp[i][j] = dp[i+1][j-1]&&s[i]==s[j]; // 注意, <len的结果是已经求出来了的
				if (dp[i][j] && ans<len)
				{
					ans = len; // 当然, 这里也可以维护一下最长回文的起始位置
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

测试数据

1
2
3
4
5
XMADAMYX
122123321
答案
5
6