通关之路
题目
分析
推荐：两星
最长回文字符串：
1.动态规划 ：dp数组是关键，理解成每一个维都一个字符串, 然后是匹配长度
dp[i][j]的意思， 从i到j都相等
2.马拉车算法(化奇偶为奇)
要点：插入#，开头入$, 求p数组, 从左往右，j点作为曾经的点已经算过
j = 2*id - i , j 是 i 关于id的对称点
3.暴力解法（中间扩展）：可以用来获取一部分分数，可以全对，判断奇偶关系即可
4.扩张KMP算法
注意：出错第一遍，先检查ONLINE_JUDGE
要点
动态规划：字符串匹配的关键在于如何利用已经计算过得部分
知识点
题解
动态规划
#include <iostream>
using namespace std;
int dp[1010][1010];
int main() {
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
string s;
getline(cin, s);
int len = s.length(), ans = 1;
///i与i，i与i-1相比较， 所有长度为2的相同已匹配完
for(int i = 0; i < len; i++) { ///找到前后一样的字母
dp[i][i] = 1;
///解决偶数的数据
if(i < len - 1 && s[i] == s[i+1]) {
dp[i][i+1] = 1;
ans = 2;
}
}
///算法复杂度近似 nlogn
///L==3 ， i = 0时， j = 2, i+1 = 1 , j - 1 = 1, 即中心位置
for(int L = 3; L <= len; L++) { ///从3开始找, 状态转移方程
for(int i = 0; i + L - 1 < len; i++) {
int j = i + L -1;
///L==3 ， i = 0时， j = 2, i+1 = 1 , j - 1 = 1, 即中心位置，状态转移
if(s[i] == s[j] && dp[i+1][j-1] == 1) {
dp[i][j] = 1;
ans = L;
}
}
}
printf("%d", ans);
return 0;
}
暴力解法
#include <iostream>
using namespace std;
int main(){
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif // ONLINE_JUDGE
string s;
int maxLength = 0;
getline(cin, s);
for(int i = 0; i < s.length(); i++){
int j = 1;
while(i - j > 0 && i+j < s.length() && s[i-j] == s[j+i])
j++;
if (maxLength < j*2-1)
maxLength = j * 2 -1;
j = i+1;
int t = i;
while(t>=0 && j<s.length() && s[t] == s[j]){
t--;j++;
}
if (maxLength < j-t-1)
maxLength = j-t-1;
}
printf("%d", maxLength);
}