#

github 地址：https://github.com/iofu728/PAT-A-by-iofu728 难度：☆☆☆ 关键词：动态规划 dp

# 题目

1040.Longest Symmetric String (25) Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given “Is PAT&TAP symmetric?”, the longest symmetric sub-string is “s PAT&TAP s”, hence you must output 11.

Input Specification:

Each input file contains one test case which gives a non-empty string of length no more than 1000.

Output Specification:

For each test case, simply print the maximum length in a line.

Sample Input: Is PAT&TAP symmetric?

Sample Output: 11

# 大意

给出一行字符串，输出之中最大对称字符子串长度。

# 思路

1. 一看到求最大子串，意识到这是一个动态规划题。而动态规划势必要建立 dp 方程。
2. 用 dp[i][j]来表示 i 点和 j 点之间子串是否对称，对称为 1.str[i]为上述字符串数组。
3. 递归方程: 若str[i]==s[j]，则dp[i][j]=dp[i+1][j-1];若str[i]!=s[j]，则dp[i][j]=0; 边界条件： dp[i][i]=1;当str[i]==str[i+1],dp[i][i+1]=1;
4. 先一遍遍历，初始化边界条件；再遍历一次，从长度为 3 开始。

# code

#include <iostream>
#include <string>
using namespace std;

const int maxn = 1002;
int dp[maxn][maxn];

int main() {
  string str;
  getline(cin, str);
  int size = str.size(), len = 1;
  for (int i = 0; i < size; ++i) {
    dp[i][i] = 1;
    if (i < size - 1 && str[i] == str[i + 1]) {
      dp[i][i + 1] = 1;
      len = 2;
    }
  }
  for (int L = 3; L <= size; ++L) {
    for (int i = 0; i + L - 1 < size; ++i) {
      int j = i + L - 1;
      if (str[i] == str[j] && dp[i + 1][j - 1] == 1) {
        dp[i][j] = 1;
        len = L;
      }
    }
  }
  cout << len << endl;
  return 0;
}