PTA 天梯赛 L2-008 最长对称子串 (25 point(s))

L2-008 最长对称子串 (25 point(s))

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

输入格式：

输入在一行中给出长度不超过1000的非空字符串。

输出格式：

在一行中输出最长对称子串的长度。

输入样例：

Is PAT&TAP symmetric?

输出样例：

思路：

首先输入一行字符串，然后去找是否有相邻两个字符是一样的，然后用字符串dp[][]（两个括号里的内容分别从表示回文子串的首尾）去记录让这个子串为1，然后长度开始从3开始，去比较s[i]和s[j]假如一样就看i+1位以及j-1位假如dp[i + 1][j - 1]为1的话，就说明之前是回文子串，那么现在也是回文子串了，这个时候记录下最大的长度就行了。

#include <iostream>
using namespace std;
const int maxn = 1010;
int dp[maxn][maxn] = {0};
int main() {
	string s;
	getline(cin, s);
	int ans = 1;
	for (int i = 0; i < s.size(); i++) {
		dp[i][i] = 1;
		if (s[i] == s[i + 1]) {
			ans = 2;
			dp[i][i + 1] = 1;
		}
	}
	for (int len = 3; len <= s.size(); len++) {
		for (int i = 0; i + len - 1 < s.size(); i++) {
			int j = i + len - 1;
			if (s[i] == s[j] && dp[i + 1][j - 1] == 1) {
				dp[i][j] = 1;
				ans = len;
			} 
		}
	}
	cout << ans << endl;
	return 0;
}