最长回文子串

主题：最长回文部分列

说明：给出字符串s，在s中找出最长的回文部分串。可以假设s的最大长度为1000。

示例：

输入： 'babad '输出： 'bab '也是有效的答案。

解析

回文字符串我们大多数人在学习编程语言基础的时候可能都练习过，只是判断了字符串是否是回文，今天的主题要复杂得多。要查找所有的子串并逐一判断其是否为回文，可能需要o(n3 )的时间复杂性，因此对其进行优化。下面介绍的两种方法可以将这个问题的时间复杂度分别降低到o(n2 )和o ) n )。

方法1 :中心扩展

回文字符串的特性是中心对称的，假设各字符是回文子串的中心字符，可以以该字符为中心向两侧扩展直到不再是回文子串为止。这样，找到了以各文字为中心的最长的回文子串。也就是说，找到了最长的回文子串。但是，这里有需要注意的事情。那就是，一个回文列的中心可能是一个文字。例如，“aba”可能以字符“b”为中心，也可能位于两个字符之间。例如，“abba”的中心位于两个“b”字符之间。如果处理这两种情况，代码就很简单了。参考如下。

publicstringlongestpalindrome{

int len=s.length (；

if(len==0)返回"；

int i=0；

int [ ] ends=新int [2]；

while(Ilen ) {

//处理“ABA”时

Getends(s，len，i-1，i 1，ends )；

//处理“ABBA”的情况

Getends(s，len，I，i 1，ends )；

I；

}

returns.substring (终端[0]，终端[1]；

}

私有视点长度(字符串、内部光线、内部左侧、内部光线、内部) {

while (左=0右；右(左)=s.Charat )右) ) {

左-----；

右；

}

if((ends[1]-ends[0] )左右-1) ) ) ) )。

ends [0]=左1；

ends [1]=右；

}

方法Manacher算法

该方法也称为马拉色算法，可以说是解决回文字符串的最佳算法。因为时间的复杂性只有o(n )。让我们逐一分析一下这个算法是如何变得如此高效的。

首先，用“#”或字符串中不存在的字符分隔字符串的各个字符，顺利插入“#”。下面是一个例子。

通过以上操作，解决了长度奇偶校验的问题，新字符串的长度为2*n 1，始终为奇数。

接下来和中心扩展一样，决定以1个字符为中心的最长回文子串的长度。 Manacher算法中有“回文半径”的概念。这是指从中心文字到最右侧(或最左侧)文字的距离。例如，“#a#”的半径为2。利用这个距离制作半径回文排列radius的话，可以从排列中的最大值决定最长回文部分排列的长度。例如，上例中中间字符“b”的回文半径为4，组成的回文数组如下：

可以看出，以原字符串的第I个字符为中心的最长回文部分列是从radius数组的第I个比特的值中减去1后得到的。那么，怎么做这个排列呢？

求出位置I (相对于I(manacher结构的字符串)的回文半径，也就是radius[i]的值，将其最右侧的位置设为mx，则如下所示。

然后计算位置j处的回文半径。其中我是ji。因为radius[i]的值可能是0或更大，所以j可能小于mx或大于mx。让我们先来看看j=mx的情况。如下所述，j

tps://p9.toutiaoimg.com/origin/pgc-image/9d1958bcf253450eb04a6cf3d0d851da?from=pc">

现在，让我们把目光聚焦到 j 的对称点 k 上，它将为我们计算 j 的回文半径提供线索。因为radius[k]的值可能很小，以 k 为中心的回文子串完全被以 i 为中心的子串覆盖，也可能较大超出了 i 的范围，如下所示：

对于第一种情况，可以肯定 j 也将被 i 完全覆盖，所以它的回文半径和 k 是相等的。第二种情况则表明从 mx 之后的部分是未知的，需要进一步计算。

现在我们再来考虑 j>=mx 的情况，如下图所示，这时 j 的回文半径一点都没计算过，所以只能进一步进行计算。

根据以上思路，可以参考的代码如下：

public String longestPalindromeOptimize(String s) { if (s == null || s.length() == 0) { return ""; } char[] 无奈的宝贝 = manacherStr(s); // 构造回文半径数组 int[] radius = new int[无奈的宝贝.length]; // 当前已经计算过的最右侧下标 int mx = -1; // i 表示 mx 最大时，对应的回文子串的中心 int i = -1; // 最长回文子串的长度 int max = 0; // 最长回文子串的起点下标 int maxIndex = -1; for (int j = 0; j < radius.length; j++) { // 2*i-j 是 j 相对于 i 的对称点，也就是文章中的 k。 // 当 j<mx 时，由于以 k 为中心的子串可能被 i 完全覆盖，也可能超出 i 的范围 // 所以，计算我们只能计算出 radius[j] 在 mx-j这个范围内的值 // 而当 j>mx 时，就需要完全从头开始计算了 radius[j] = j < mx ? Math.min(radius[2 * i - j], mx - j + 1) : 1; // 计算 j<mx 时超出 mx-j 范围内的部分，或者 j 本就大于 mx时 while (j + radius[j] < 无奈的宝贝.length && j - radius[j] >= 0 && 无奈的宝贝[j - radius[j]] == 无奈的宝贝[j + radius[j]]) { radius[j]++; } // 更新 mx 的值和 i 的值 if (j+radius[j]>mx) { mx = j+radius[j]-1; i = j; } // 更新max的值 if (max<radius[j]) { max = radius[j]; // j 的起点坐标，相对于Manacher字符数组而言是 j-radius[j]+1 // 而相对于原数组而言，这个值是由原数组的位置乘以2再加一得到的，所以直接除以2即可 maxIndex = (j-radius[j]+1)/2; } } return s.substring(maxIndex,maxIndex+max-1); } private char[] manacherStr(String s){ StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { sb.append('#'); sb.append(s.charAt(i)); } sb.append('#'); return sb.toString().toCharArray(); }

总结

Manacher算法如果我们没有听过还是很难想到的，不过不要气馁，我们只是来学习的，想不到能学到也算赚到，能够理解它也算一笔不小的收获。下面这个题目较为简单，让我们放松一下吧。

下题预告

题目：Z 字形变换

描述：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L C I R E T O E S I I G E D H N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows);

示例 1：

输入: s = "LEETCODEISHIRING", numRows = 3输出: "LCIRETOESIIGEDHN"

示例 2：

输入: 输入: s = "LEETCODEISHIRING", numRows = 4输出: "LDREOEIIECIHNTSG"解释： L D R E O E I I E C I H N T S G

最长回文子串c语言(字符串最长回文)

最长回文子串

解析

总结

下题预告