java最长回文子串（Manacher算法的详细讲解）

本文目录

• Manacher算法的详细讲解
• java 编写一个方法,找出一个字符串中最长的回文子串
• 巧用贪心算法，计算出字符串回文

Manacher算法的详细讲解

Manacher算法，又叫“马拉车”算法，可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题。

比较简单的思路是将字符串的每一个字符作为回文子串的中心对称点，每次保存前面求得的回文子串的最大值，最后得到的就是最长的回文子串的长度，这种方式的时间复杂度是O(n^2)。在求解过程中，基数的回文子串与偶数的回文子串是不一样的。比如最长回文子串为aba，对称中心就是b，如果最长回文子串为abba，则对称中心应该为两个b之间，为了解决这个问题，可以在每个字符两边加上一个符号，具体什么符号（是字符串里面的符号也行）对结果没有影响，比如加上“#”，则上述的两个序列变成了#a#b#a#和#a#b#b#a#，求出的长度分别为6和9，再除以2就可以得到最后的结果3和4。这种方式的时间复杂度太高，下面介绍时间复杂度为O(n)的Manacher算法。

在进行Manacher算法时，字符串都会进行上面的进入一个字符处理，比如输入的字符为acbbcbds，用“#”字符处理之后的新字符串就是#a#c#b#b#c#b#d#s#。

回文半径数组radius是用来记录以每个位置的字符为回文中心求出的回文半径长度，如下图所示，对于p1所指的位置radius。

一个位置最右回文右边界指的是这个位置及之前的位置的回文子串，所到达的最右边的地方。比如对于字符串#a#c#b#b#c#b#d#s#，求它的每个位置的过程如下：

最开始的时候R=-1，到p=0的位置，回文就是其本身，最右回文右边界R=0;p=1时，有回文串#a#，R=2；p=2时，R=2;P=3时，R=6;p=4时，最右回文右边界还是p=3时的右边界，R=6,依次类推。

就是上面提到的最右回文右边界的中心点C，如下图，p=4时，R=6，C=3

首先大的方面分为两种情况：

第一种情况：下一个要移动的位置在最右回文右边界R的右边。

比如在最开始时，R=-1,p的下一个移动的位置为p=0，p=0在R=-1的右边；p=0时，此时的R=0，p的下一个移动位置为p=1，也在R=0的右边。

在这种情况下，采用普遍的解法，将移动的位置为对称中心，向两边扩，同时更新回文半径数组，最右回文右边界R和最右回文右边界的对称中心C。

第二种情况：下一个要移动的位置就是最右回文右边界R或是在R的左边

在这种情况下又分为三种：

1、下一个要移动的位置p1 不在 最右回文右边界R右边，且cL《pL。

p2是p1以C为对称中心的对称点；

pL是以p2为对称中心的回文子串的左边界;

cL是以C为对称中心的回文子串的左边界。

这种情况下p1的回文半径就是p2的回文半径radius。

2、下一个要移动的位置票p1 不在 最右回文右边界R的右边，且cL》pL。

p2是p1以C为对称中心的对称点；

pL是以p2为对称中心的回文子串的左边界；

cL是以C为对称中心的回文子串的左边界。

这种情况下p1的回文半径就是p1到R的距离R-p1+1。

3、下一个要移动的位置票p1 不在 最右回文右边界R的右边，且cL=pL；

p2是p1以C为对称中心的对称点；

pL是以p2为对称中心的回文子串的左边界；

cL是以C为对称中心的回文子串的左边界。

这种情况下p1的回文半径就还要继续往外扩，但是只需要从R之后往外扩就可以了，扩了之后更新R和C。

从上面的分析中，可以看出，第二种情况的1，2的求某个位置的回文半径的时间复杂度是O(1)，对于第一种情况和第二种情况的3，R是不断的向外扩的，不会往回退，而且寻找回文半径时，R之内的位置是不是进行判断的，所以对整个字符串而且，R的移动是从字符串的起点移动到终点，时间复杂度是O(n),所以整个manacher的时间复杂度是O(n)。

java 编写一个方法,找出一个字符串中最长的回文子串

Java code
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.ArrayList;
import java.util.List;
public class Palindrome {
/* 找出一个字符串中最长的回文子串
* 从字符串中第i个字符开始的所有非空回文子串的个数, 记作为Ci. 此方法的复杂度为
* O(C1 + C2 + ... + Cn)
* 当字符串中任意两个非空回文子串的起始位置不同时, C1 = C2 = ... = Cn = 1, 复杂度为O(N);
* 当字符串所有字符均为同一字符时, Ci = n - i, 此时复杂度为O(N*N);
* 在多数情况下, 此方法的复杂度远低于O(N*N).
*/
public List《String》 getLongestPalindrome(String theString) {
int strLen = theString.length();
List《String》 results = new ArrayList《String》(strLen);
if (strLen == 0) {
return results;
}
// 从第i个位置开始的所有回文子串的结束位置.
int;
// endIndice中有效数据的长度.
int numberOfPalindromes = 1;
// 最长回文子串的长度. 对于非空串至少可以找到长度为1的回文子串.
int maxLen = 1;
results.add(theString.substring(strLen - 1));
// 计算从第i个位置开始的所有回文子串. 这样的子串分为三种:
// 1. 在从第i+1个位置开始的回文子串的基础上, 在两端加上相同的字符;
// 2. 长度为1的回文子串;
// 3. 空串.
for (int i = strLen - 2; i 》= 0; i--) {
int j = 0, k = 0;
while (j 《 numberOfPalindromes) {
if (theString.charAt(i) == theString.charAt(endIndice)) {
endIndice + 1;
int newLength = endIndice - i;
if (newLength 》= maxLen) {
if (newLength 》 maxLen) {
maxLen = newLength;
results.clear();
}
results.add(theString.substring(i, endIndice));
}
if (endIndice 《 strLen) {
k++;
}
}
j++;
}
// 加入长度为1的子串
endIndice = i + 1;
if (maxLen == 1) {
results.add(theString.substring(i, i + 1));
}
// 加入空串
endIndice = i;
numberOfPalindromes = k;
}
return results;
}
public static void main(String args) {
Palindrome p = new Palindrome();
printList(p.getLongestPalindrome("gabcecbaefd"));
printList(p.getLongestPalindrome("bbcbaefccfg"));
printList(p.getLongestPalindrome("aaaaaaaaaaa"));
printList(p.getLongestPalindrome("abcdefghijk"));
printList(p.getLongestPalindrome("abcdeeddejk"));
printList(p.getLongestPalindrome(""));
}
public static void printList(List《? extends Object》 list) {
System.out.println("**************************");
System.out.println(list.size() + " result(s):");
for (Object o : list) {
System.out.println(o);
}
}
}

巧用贪心算法，计算出字符串回文

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例 1:

输入:
"abccccdd"

输出:
7

解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

请注意！！！

题目的意思是：利用这个字符串中的所有字母来构造最长回文串，是构造！是可以改变字母出现的位置顺序的！字母位置可以任意移动。而不是在顺序不变的情况下找出最长的回文串。

作者一开始粗心大意没理解题意，直接上手做题吃大亏（捂脸。

现在来解释下，什么是回文？

回文串是一个正着读和反着读都一样的字符串。

来看两个不同的回文例子：

AB|BA。仅看字母，我们发现，AB和BA根据中心竖线|对称，这个回文串长度为4，每个字母出现的次数都是偶数。
ABCBA。我们发现，AB和BA根据字母C对称，这个回文串长度为5，除了对称中心的字母C仅出现过一次外，中心两边的字母出现次数都是偶数。
所以我们可以总结出，如果想要构造出一个回文串，除了回文串中心的字母只能出现一次外（如果有中心字母的话），中心两边的字母还需对称出现，即出现偶数次。

解决了构造回文串这一关键点，题目中还有一个特别之处：仅出现大写字母和小写字母。

如果对英文字母的Unicode编码熟悉的话，可以知道，字母A的Unicode编码是65（十进制），字母Z的Unicode编码是90（十进制），字母a的Unicode编码是97（十进制）,字母z的Unicode编码是122（十进制）。

可以发现它们是Unicode编码是连续（中间的91到96并不重要），即有序的，所以可以使用数组来存放它们，每个数组项的值就是每个字母出现的次数。

这种情况下，使用数组来存储，会比使用哈希表（Map）来存储来得更高性能，哪怕Unicode编码的91到97我们无需使用。

且，在JavaScript世界中，可以使用String.prototype.charCodeAt()这一API来获取Unicode编码单元。

所以，我们可以这样来统计每个字母出现的次数：