------------6.11更新-----------
明天（tuo yan）继续把 Basic & Tall刷了，改日再战
------------Original------------
为什么说这个是个经典DP呢，它经典到与最长公共子序列一样经典.
几万种变体：
这里我要来归纳一下，免得有人像我一样被虐成狗.
Short - 求给定串的最长回文子串
Basic - 给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数. ---->这是个回文子序列，不是回文子串，别尼玛搞混了
Tall.. - 给定一个数字串digit_str,每次操作可以把相邻2个数字相加并替换掉这2个数字,问至少操作几次可以得到一个回文数字串？输出最少操作次数.
(to be added)
Short(超小杯)
基本的最长回文子串.
有暴力/DP/Manacher三种算法.
其中Manacher马拉车算法是利用了回文串的特性，做到了尽可能利用已知信息，达到了O(N)时间复杂度.
基本上搜索一下都可以找到很多信息.
暴力
不多说，如果笔试肯定超时.
枚举子串时可以按照子串的长度从1 .. str.size()来枚举.
时间复杂度 - O(N3),网上大多数都说O(N3)，但我觉得应该是在O(N2)和O(N3)之间.------------->好好地估算过了确实是个O(N3)级数.(只不过这个乘了一个`x/1`的系数，无关紧要了反正还是O(N3))
DP法
第一时间想到用F[i,j]表示i..j的最长回文子串长度.马上就有F[0,l-1]就是这里需要求的整个串的最长回文子串长度.
- 错误的DP状态转移方程
我第一时间写下了这样的转移方程：F[i,j] = max { F[i+1, j-1] + 2 ----- if str[i] == str[j] ///fatal error here：如果i+1..j-1非回文但又有str[i] == str[j]怎么办？ F[i+1,j] ----- otherwise1 F[i,j-1] ----- otherwise2 }
错误的点正是这里,F[i,j] = F[i+1,j-1]+2的条件是比较严格的.
- 正确的DP状态转移方程 0x1
F[i,j] = max { F[i+1, j-1] + 2 ----- if str[i] == str[j] && F[i+1, j-1] == j-1-(i+1)+1 ////如果i+1..j-1非回文但又有str[i] == str[j]怎么办？ F[i+1,j] ----- otherwise1 F[i,j-1] ----- otherwise2 }
或者是网上其他人给的true/false矩阵，然后需要2个变量每次更新一下最长子串的长度和起始点.
- 正确的DP状态转移方程 0x2
isP[i,j] = { isP[i+1,j-1] ----- if str[i] == str[j] false ----- otherwise } - DP的填表方向/初始状态 ---- 不多说
Manacher法
也不多说,这个网上有很多详解的.
实现
- 代码()
有兴趣的同学一起来搞:<a href = https://github.com/exctPuzzles/exctpuzzs/blob/master/solutions/algs/max_plalindrome_substr.cc>github_page</a>
include <cstdio>
#include <string>
using namespace std;
#define Max(a,b) ((a) > (b) ? (a):(b))
#define Min(a,b) ((a) < (b) ? (a):(b))
#define SIZE 1005
//#define DBG_1
#define DBG_2
string::size_type F[SIZE][SIZE];//the length array
//auto init to zero
string::size_type ST[SIZE][SIZE];//the start_ofs array
class Solution {
public:
bool isP(string &x, string::size_type st, string::size_type len){
string::size_type ed = st + len - 1;
while(st < ed){
if(x[st] != x[ed]){
return false;
}
st++;ed--;
}
return true;
}
string max_plalindrome_substr_bf(string x){
//just simply find all substring & see if plalindrome.
//time complexity - O(N^3)
//a little bit optimize
string::size_type l = x.size(), i, st, max_l = 1, st_l;
for(i = 2; i <= l;i++){
for(st = 0; st + i - 1 < l ; st++){
if(max_l >= i){
break;
}
if(isP(x, st, i)){
max_l = i;
st_l = st;
}
}
}
#ifdef DBG_2
for(i = 0; i < st_l; i++){
printf(" ");
}
printf("%s\n", x.substr(st_l, max_l).c_str());
#endif
return x.substr(st_l, max_l);
}
string max_plalindrome_substr_dp(string x){
//
//time complexity - O(N^2) , space complexity - O(N^2)
//
string::size_type st_l, max_l, l = x.size(), i, st, ed;
string::size_type a,b,c;
for(i = 0; i < l; i++){
F[i][i] = 1;
ST[i][i] = i;
}
for(i = 2; i <= l; i++){//for every substring's length,direction to fill the DP array
for(st = 0; (ed = st + i - 1) < l; st++){
//a = x[st] == x[ed] ? F[st + 1][ed - 1] + 2 : 0;/////a fatal bug here
a = x[st] == x[ed] && F[st + 1][ed - 1] == ed - 1 - st? F[st + 1][ed - 1] + 2 : 0;//the situation left for b&c
b = F[st + 1][ed];
c = F[st][ed - 1];
if(a > b){
if(a > c){
F[st][ed] = a;
ST[st][ed] = st;
}else{
F[st][ed] = c;
ST[st][ed] = ST[st][ed - 1];
}
}else{
if(b > c){
F[st][ed] = b;
ST[st][ed] = ST[st + 1][ed];
}else{
F[st][ed] = c;
ST[st][ed] = ST[st][ed - 1];//bug fix
}
}
}
}
#ifdef DBG_1
for(i = 0; i < l; i++){
for(string::value_type j = 0; j < l; j++){
printf("%ld ", F[i][j]);
}
printf("\n");
}
#endif
#ifdef DBG_2
for(i = 0; i < ST[0][l-1]; i++){
printf(" ");
}
printf("%s\n", x.substr(ST[0][l-1], F[0][l-1]).c_str());
#endif
return x.substr(ST[0][l-1], F[0][l-1]);
}
bool isP_arr[SIZE][SIZE];
string max_plalindrome_substr_dp2(string s){
string::size_type i, l = s.size(), st, ed, max_l = 1, max_st;
for(i = 0; i < l; i++){//len = 1
isP_arr[i][i] = true;
isP_arr[i+1][i] = true;
}
for(i = 2; i <= l; i++){
for(st = 0; (ed = st + i - 1) < l; st++){
isP_arr[st][ed] = s[st] == s[ed] ? isP_arr[st+1][ed-1] : false;
if(isP_arr[st][ed] && i > max_l){
max_l = i;
max_st = st;
}
}
}
#ifdef DBG_2
for(i = 0; i < max_st; i++){
printf(" ");
}
printf("%s\n", s.substr(max_st, max_l).c_str());
#endif
return s.substr(max_st, max_l);
}
#define dou_SIZE 2010
string max_plalindrome_substr_mnc(string s){
string tmp(s);
string::size_type po, r_mx, Len[dou_SIZE], i, j, mx_iter, l, rt, lt;
for(i = 0; i <= s.size(); i++){
tmp.insert( 2 * i, "#");
}//convert the string to #s#t#r#i#n#g#
// printf("%s\n", tmp.c_str());
l = tmp.size();
po = 0;
r_mx = 0;
string::size_type start_point, mirr, length;
for(i = 0; i < l; i++){//calc Len[i]
if(i < r_mx){
mirr = 2 * po - i;
if(Len[mirr] >= r_mx - i + 1){
Len[i] = r_mx - i + 1;
start_point = r_mx - i + 1;
}else{
Len[i] = Len[mirr];
continue;
}
}else{
Len[i] = 1;////
start_point = 1;
}
mx_iter = Min(i - 0 + 1, l - 1 - i + 1 ) - 1;
for(j = start_point/**/; j <= mx_iter; j++){
lt = i - j;
rt = i + j;
if(tmp[lt] == tmp[rt]){
Len[i]++;
if(Len[i] > r_mx - po + 1){
po = i;
r_mx = po + Len[i] - 1;
}
}else{
break;
}
}
}
if(tmp[po] == '#'){
start_point = po/2 - (Len[po] - 1)/2;
length = (Len[po] - 1);
}else{
length = (Len[po] - 1);
start_point = (po-1)/2 - (length - 1)/2;
}
#ifdef DBG_2
for(i = 0; i < start_point; i++){
printf(" ");
}
printf("%s\n", s.substr(start_point, length).c_str());
#endif
return s.substr(start_point, length);
}
string longestPalindrome(string s) {
string ret;
#ifdef DBG_2
printf("%s\n", s.c_str());
ret = max_plalindrome_substr_bf(s);
printf("==============================================\n");
printf("%s\n", s.c_str());
max_plalindrome_substr_dp(s);
printf("==============================================\n");
printf("%s\n", s.c_str());
max_plalindrome_substr_dp2(s);
printf("==============================================\n");
printf("%s\n", s.c_str());
max_plalindrome_substr_mnc(s);
#endif
return ret;
}
};
#include <iostream>
int main()
{
Solution s;
string str;
while(getline(cin, str)){
s.longestPalindrome(str);
//printf("longest palindromic substr - %s\n", s.longestPalindrome(str2).c_str());
}
return 0;
}
```
- 测试 - leetcode/5.longest palindromic substring 通过.
echo "zgtklhfzomzjckwmluvivvcmhjrwkuvcjrxojobpdedpamdshcwwsetfbacvonecrdvugeibglvhxuymjvoryqjwullvzglqazxrdmczyvbgakjagttrezmvrlptiwoqkrtxuroeqmryzsgokopxxdpbejmtwvpnaqrgqladdszhdwxfckmewhdvihgvacueqhvwvjxoitlpfrckxkuksaqzjpwgoldyhugsacflcdqhifldoaphgdbhaciixouavqxwlghadmfortqacbffqzocinvuqpjthgekunjsstukeiffjipzzabkuiueqnjgkuiojwbjzfynafnlcaryygqjfixaoeowhkxkbsnpsvnbxuywfxbnuoemxynbtgkqtjvzqikbafjnpbeirxxrohhnjqrbqqzercqcrcswojyylunuevtdhamlkzqnjrzibwckbkiygysuaxpjrgjmurrohkhvjpmwmmtpcszpihcntyivrjplhyrqftghglkvqeidyhtmrlcljngeyaefxnywpfsualufjwnffyqnpitgkkyrbwccqggycrvoocbwsdbftkigrkcbojuwwctknzzmvhbhbfzrqwzllulbabztqnznkqdyoqnrxhwavqhzyzvmmmphzxbikpharseywpfsqyybkynwbdrgfsaxduxojcdqcjuaywzbvdjgjqtoffasiuhvxcaockebkuxpiomqmtvsqhnyxfjceqevqvnapbk " | ./test > 1.txt
zgtklhfzomzjckwmluvivvcmhjrwkuvcjrxojobpdedpamdshcwwsetfbacvonecrdvugeibglvhxuymjvoryqjwullvzglqazxrdmczyvbgakjagttrezmvrlptiwoqkrtxuroeqmryzsgokopxxdpbejmtwvpnaqrgqladdszhdwxfckmewhdvihgvacueqhvwvjxoitlpfrckxkuksaqzjpwgoldyhugsacflcdqhifldoaphgdbhaciixouavqxwlghadmfortqacbffqzocinvuqpjthgekunjsstukeiffjipzzabkuiueqnjgkuiojwbjzfynafnlcaryygqjfixaoeowhkxkbsnpsvnbxuywfxbnuoemxynbtgkqtjvzqikbafjnpbeirxxrohhnjqrbqqzercqcrcswojyylunuevtdhamlkzqnjrzibwckbkiygysuaxpjrgjmurrohkhvjpmwmmtpcszpihcntyivrjplhyrqftghglkvqeidyhtmrlcljngeyaefxnywpfsualufjwnffyqnpitgkkyrbwccqggycrvoocbwsdbftkigrkcbojuwwctknzzmvhbhbfzrqwzllulbabztqnznkqdyoqnrxhwavqhzyzvmmmphzxbikpharseywpfsqyybkynwbdrgfsaxduxojcdqcjuaywzbvdjgjqtoffasiuhvxcaockebkuxpiomqmtvsqhnyxfjceqevqvnapbk
pdedp
==============================================
zgtklhfzomzjckwmluvivvcmhjrwkuvcjrxojobpdedpamdshcwwsetfbacvonecrdvugeibglvhxuymjvoryqjwullvzglqazxrdmczyvbgakjagttrezmvrlptiwoqkrtxuroeqmryzsgokopxxdpbejmtwvpnaqrgqladdszhdwxfckmewhdvihgvacueqhvwvjxoitlpfrckxkuksaqzjpwgoldyhugsacflcdqhifldoaphgdbhaciixouavqxwlghadmfortqacbffqzocinvuqpjthgekunjsstukeiffjipzzabkuiueqnjgkuiojwbjzfynafnlcaryygqjfixaoeowhkxkbsnpsvnbxuywfxbnuoemxynbtgkqtjvzqikbafjnpbeirxxrohhnjqrbqqzercqcrcswojyylunuevtdhamlkzqnjrzibwckbkiygysuaxpjrgjmurrohkhvjpmwmmtpcszpihcntyivrjplhyrqftghglkvqeidyhtmrlcljngeyaefxnywpfsualufjwnffyqnpitgkkyrbwccqggycrvoocbwsdbftkigrkcbojuwwctknzzmvhbhbfzrqwzllulbabztqnznkqdyoqnrxhwavqhzyzvmmmphzxbikpharseywpfsqyybkynwbdrgfsaxduxojcdqcjuaywzbvdjgjqtoffasiuhvxcaockebkuxpiomqmtvsqhnyxfjceqevqvnapbk
pdedp
==============================================
zgtklhfzomzjckwmluvivvcmhjrwkuvcjrxojobpdedpamdshcwwsetfbacvonecrdvugeibglvhxuymjvoryqjwullvzglqazxrdmczyvbgakjagttrezmvrlptiwoqkrtxuroeqmryzsgokopxxdpbejmtwvpnaqrgqladdszhdwxfckmewhdvihgvacueqhvwvjxoitlpfrckxkuksaqzjpwgoldyhugsacflcdqhifldoaphgdbhaciixouavqxwlghadmfortqacbffqzocinvuqpjthgekunjsstukeiffjipzzabkuiueqnjgkuiojwbjzfynafnlcaryygqjfixaoeowhkxkbsnpsvnbxuywfxbnuoemxynbtgkqtjvzqikbafjnpbeirxxrohhnjqrbqqzercqcrcswojyylunuevtdhamlkzqnjrzibwckbkiygysuaxpjrgjmurrohkhvjpmwmmtpcszpihcntyivrjplhyrqftghglkvqeidyhtmrlcljngeyaefxnywpfsualufjwnffyqnpitgkkyrbwccqggycrvoocbwsdbftkigrkcbojuwwctknzzmvhbhbfzrqwzllulbabztqnznkqdyoqnrxhwavqhzyzvmmmphzxbikpharseywpfsqyybkynwbdrgfsaxduxojcdqcjuaywzbvdjgjqtoffasiuhvxcaockebkuxpiomqmtvsqhnyxfjceqevqvnapbk
pdedp
==============================================
zgtklhfzomzjckwmluvivvcmhjrwkuvcjrxojobpdedpamdshcwwsetfbacvonecrdvugeibglvhxuymjvoryqjwullvzglqazxrdmczyvbgakjagttrezmvrlptiwoqkrtxuroeqmryzsgokopxxdpbejmtwvpnaqrgqladdszhdwxfckmewhdvihgvacueqhvwvjxoitlpfrckxkuksaqzjpwgoldyhugsacflcdqhifldoaphgdbhaciixouavqxwlghadmfortqacbffqzocinvuqpjthgekunjsstukeiffjipzzabkuiueqnjgkuiojwbjzfynafnlcaryygqjfixaoeowhkxkbsnpsvnbxuywfxbnuoemxynbtgkqtjvzqikbafjnpbeirxxrohhnjqrbqqzercqcrcswojyylunuevtdhamlkzqnjrzibwckbkiygysuaxpjrgjmurrohkhvjpmwmmtpcszpihcntyivrjplhyrqftghglkvqeidyhtmrlcljngeyaefxnywpfsualufjwnffyqnpitgkkyrbwccqggycrvoocbwsdbftkigrkcbojuwwctknzzmvhbhbfzrqwzllulbabztqnznkqdyoqnrxhwavqhzyzvmmmphzxbikpharseywpfsqyybkynwbdrgfsaxduxojcdqcjuaywzbvdjgjqtoffasiuhvxcaockebkuxpiomqmtvsqhnyxfjceqevqvnapbk
pdedp
想做成一件事最好的办法就是——做他
Just father Fucking Do it.
网友评论