PAT(动态规划)——1040. Longest Symmetric String (25)-PAT甲级真题（动态规划）

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

分析：dp[i][j]表示s[i]到s[j]所表示的字串是否是回文字串。只有0和1，递推方程为：

1 当s[i] == s[j] : dp[i][j] = dp[i+1][j-1]

2 当s[i] != s[j] : dp[i][j] =0

3 边界：dp[i][i] = 1, dp[i][i+1] = (s[i] == s[i+1]) ? 1 : 0因为i、j如果从小到大的顺序来枚举的话，无法保证更新dp[i][j]的时候dp[i+1][j-1]已经被计算过。因此不妨考虑按照字串的长度和子串的初试位置进行枚举，即第一遍将长度为3的子串的dp的值全部求出，第二遍通过第一遍结果计算出长度为4的子串的dp的值…这样就可以避免状态无法转移的问题

首先初始化dp[i][i] = 1, dp[i][i+1]，把长度为1和2的都初始化好，然后从L = 3开始一直到 L <= len 根据动态规划的递归方程来判断

题目大意：

题目解析：

马拉车算法：https://blog.csdn.net/liuwei0604/article/details/50414542
说明一下，不加这两行代码会报段错误。

str.resize(MAXN);
    s.resize(MAXN);

具体代码：

#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define MAXN 2010
int p[MAXN];
string str,s;
int n;
void init(){
	s[0]='$';
	s[1]='#';
	n=str.size();
	for(int i=0;i<n;i++){
		s[i*2+2]=str[i];
		s[i*2+3]='#';
	}
	n=n*2+2;
	s[n]=0;
}
void solve(){
	int mx=0;
	int id;
	for(int i=1;i<n;i++){
		if(mx>i)
			p[i]=min(p[2*id-i],p[id]+id-i);
		else
			p[i]=1;
		for(;s[i+p[i]]==s[i-p[i]];p[i]++);
		if(p[i]+i>mx){
			mx=p[i]+i;
			id=i;
		}
	}
}
int main()
{
    str.resize(MAXN);
    s.resize(MAXN);
    getline(cin,str);
    init();
    solve();
    int maxlen=-1;
    for(int i=0;i<n;i++)
    	if(p[i]>maxlen)
    		maxlen=p[i];
    printf("%d",maxlen-1);
    return 0;
}