JiaHeng-DLUT
8/15/2019 - 4:08 AM

Longest Symmetric Substring

最长回文子串

Q

求字符串 S 的最长回文子串的长度。

Sample Input:
PATZJUJZTACCBCC
Sample Output:
9 (ATZJUJZTA)

A

  • dp[i][j] : S[i] 至 S[j] 所表示的子串是否是回文子串，是则是 1 ，不是则为 0 。
  • return max(dp)
  • dp[i][j] = dp[i + 1][j - 1], S[i] == S[j]
  • dp[i][j] = 0, S[i] != S[j]
  • dp[i][i] = 1, dp[i][i+1] = (S[i] == S[i + 1]) ? 1 : 0
  • O(n^2)

最长回文子串问题还有一些其他做法，例如 二分 + 字符串 hash 复杂度为 O(n logn) ，最优秀的当属复杂度为 O(n) 的 Manacher 算法。

LSS.cpp
content_copyfile_download
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int N;
const int MAX_N = 1e3 + 5;
string S;
int dp[MAX_N][MAX_N];

int main() {
	getline(cin, S);
	int len = S.size(), ans = 1;
	memset(dp, 0, sizeof(dp));

	// boundary
	for (int i = 0; i < len; i++) {
		dp[i][i] = 1;
		if (i < len - 1) {
			if (S[i] == S[i + 1]) {
				dp[i][i + 1] = 1;
				ans = 2;
			}
		}
	}

	// state transition equation
	for (int l = 3; l <= len; l++) {
		for (int i = 0; i + l - 1 < len; i++) {
			int j = i + l - 1;
			if (S[i] == S[j] && dp[i + 1][j - 1] == 1) {
				dp[i][j] = 1;
				ans = l;
			}
		}
	}

	cout << ans << endl;
	return 0;
}

/*
Sample Input:
PATZJUJZTACCBCC
Sample Output:
9 (ATZJUJZTA)
*/