[算法] 最长回文子串
题目:找出一个字符串中的最长回文子串!
回文字符串的子串也是回文,比如P[i,j](表示以i开始以j结束的子串)是回文字符串,那么P[i + 1, j - 1]也是回文字符串,这样最长回文子串就能分解成一系列子问题了。
首先定义状态方程和转移方程,P[i,j] = 0表示子串[i,j]不是回文子串,P[i,j] = 1表示子串[i, j]是回文子串:
123P[i, i] = 1;P[i, ...
阅读全文…