大家好，又见面了，我是你们的朋友全栈君。
最长回文子串的问题描述：
给出一个字符串S，求S的最长回文子串的长度。
样例：
字符串“PATZJUJZTACCBCC”的最长回文子串为“ATZJUJZTA”，长度为9。
先看暴力解法：枚举子串的两个端点i和j，判断在i，区间内的子串是否回文。
从复杂度上来看，枚举端点需要O（n2），判断回文需要O（n），因此总复杂度是O（n3）。
介绍动态规划的方法，使用动态规划可以达到更优的0（n2）复杂度，而最长回文子串有很多种使用动态规划的方法，这里介绍其中最容易理解的一种。
令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是则为1，不是为0。这样根据S[i]是否等于S[j]，可以把转移情况分为两类：
①若S[i] = S[j]，那么只要S[i+1]至S[j-1]是回文子串，S[i]至S[j]就是回文子串；如果S[i+1]至S[j-1]不是回文子串，则S[i]至S[j]也不是回文子串。
②若S[i]！=S[j]，那么S[i]至S[j]一定不是回文子串。
写出状态转移方程：
边界：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]已经被计算过，从而无法得到正确的dp[i][j]。
先固定i=0，然后枚举j从2开始。
当求解dp[0][2]时，将会转换为dp[1][1]，而dp[1][1]是在初始化中得到的；
当求解dp[0][3]时，将会转换为dp[1][2]，而dp[1][2]也是在初始化中得到的；
当求解dp[0][4]时，将会转换为dp[1][3]，但是dp[1][3]并不是已经计算过的值，因此无法状态转移。
事实上，无论对i和j的枚举顺序做何调整，都无法调和这个矛盾，因此必须想办法寻找新的枚举方式。
根据递推写法从边界出发的原理，注意到边界表示的是长度为1和2的子串，且每次转移时都对子串的长度减了1，因此不妨考虑按子串的长度和子串的初始位置进行枚举，
即第一遍将长度为3的子串的dp值全部求出，
第二遍通过第一遍结果计算出长度为4的子串的dp值……这样就可以避免状态无法转移的问题。
最普通的遍历O(n3)
void way1()
{
for (int i = 0; i < str.length(); ++i)
{
for (int j = str.length() - 1; j > i; --j)
{
t1.assign(str.begin() + i, str.begin() + j + 1);
t2.assign(t1.rbegin(), t1.rend());
if (t1 == t2)
res = res > t1.length() ? res : t1.length();
}
}
}利用回文子串中心的两边相同
void way2()
{
for (int i = 0; i < str.size(); ++i) {
int j;
for (j = 1; i - j >= 0 && i + j < str.size() && str[i + j] == str[i - j]; ++j);//以当前字符为回文中心查找最长回文子串
res= max(res, 2 * j - 1);//更新回文子串最大长度
for (j = 0; i - j >= 0 && i + j + 1 < str.size() && str[i - j] == str[i + 1 + j]; ++j);//以当前字符为回文中心左侧字符查找最长回文子串
res = max(res, 2 * j);//更新回文子串最大长度
}
}使用动态规划
void way3()
{
int dp[1010][1010];
for (int i = 0; i < str.length(); i++)
{
dp[i][i] = 1;//边界
if (i < str.length() - 1 && str[i] == str[i + 1])
{
dp[i][i + 1] = 1;//边界
res = 2;
}
}
for (int L = 3; L <= str.length(); L++) {//因为上面已经初始化了长度L==1和L==2的情形
for (int i = 0; i + L - 1 < str.length(); i++) {
int j = i + L - 1;
if (str[i] == str[j] && dp[i + 1][j - 1] == 1) {
dp[i][j] = 1;
res = L;
}
}
}
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/143072.html原文链接：https://javaforall.net
