思路
- 在字符串s中，用rad[i]表示第i个字符的回文半径，即rad[i]尽可能大，且满足：
s[i-m] = si+m - 将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。
假设现在求出了rad[1..i-1]，现在要求后面的rad值，并且通过前面的操作，得知了当前字符i的rad值至少为j，现在通过试图扩大j来扫描，求出了rad[i]。再假设现在有个指针k，从1循环到rad[i]，试图通过某些手段来求出[i+1,i+rad[i]]的rad值。
根据定义，黑色的部分是一个回文子串，两段红色的区间全等。
因为之前已经求出了rad[i-k]，所以直接用它.有3种情况：
（1）rad[i]-k < rad[i-k]
如图,rad[i-k]的范围为青色。因为黑色的部分是回文的，且青色的部分超过了黑色的部分，所以rad[i+k]肯定至少为rad[i]-k，即橙色的部分。那橙色以外的部分就不是了吗？这是肯定的。因为如果橙色以外的部分也是回文的，那么根据青色和红色部分的关系，可以证明黑色部分再往外延伸一点也是一个回文子串，这肯定不可能，因此rad[i+k] = rad[i]-k
（2）rad[i]-k > rad[i-k]
如图,rad[i-k]的范围为青色。因为黑色的部分是回文的，且青色的部分在黑色的部分里面，根据定义，很容易得出：rad[i+k] = rad[i-k]
根据上面两种情况，可以得出结论：当rad[i]-k! = rad[i-k]的时候，rad[i+k] = min(rad[i]-k,rad[i-k])。
（3）rad[i]-k = rad[i-k]
如图，通过和第一种情况对比之后会发现，因为青色的部分没有超出黑色的部分，所以即使橙色的部分全等，也无法像第一种情况一样引出矛盾，因此橙色的部分是有可能全等的。但是，根据已知的信息，我们不知道橙色的部分是多长，因此就把i指针移到i+k的位置，j=radi-k，等下次循环的时候再做了。
整个算法就这样。
至于时间复杂度为什么是O(n)
/**
* 对称字符串的最大长度（字符串）<br/>
* 题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。<br/>
* 比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
*
* @author Joeson
*
*/
public class MainTest {
public static void main(String[] args) {
String s = "acbcasacbcd";
long pre = System.currentTimeMillis();
char[] str = init(s);
System.out.println(Arrays.toString(str));
manacher(str);
System.out.println("用时：" + (System.currentTimeMillis() - pre)+"ms");
}
/**
* 返回例如 #a#c#b#c#a#a#c#b#c#d#形式的字符串数组
*
* @param s
* @return
*/
public static char[] init(String s) {
char[] str = new char[s.length() * 2 + 1];
int i = 0;
for (; i < s.length(); i++) {
str[2 * i] = '#';
str[2 * i + 1] = s.charAt(i);
}
str[2 * i] = '#';
return str;
}
/**
*
*
* @param str
*/
public static void manacher(char[] s) {
int rad[] = new int[s.length];
int i = 1, j = 0, k;
// 记录最长的回文串的长度
int maxLen = 0;
while (i < s.length) {
// 扫描得出rad值
while (i - j - 1 > -1 && i + j + 1 < s.length && s[i - j - 1] == s[i + j + 1])
j++;
rad[i] = j;
maxLen = maxLen > j ? maxLen : j;
k = 1;
while (k <= rad[i] && rad[i - k] != rad[i] - k) {
rad[i + k] = Math.min(rad[i - k], rad[i] - k);
k++;
}
i = i + k;
j = Math.max(j - k, 0);
}
System.out.println(Arrays.toString(rad));
System.out.println("最长回文串长度： " + maxLen);
}
}
Paste_Image.png
解法二
思路来源于 8皇后问题
private static int manacherIndex[];
public static void main(String[] args) {
String s = "acbcasacbcd";
manacherIndex = new int[s.length()];
long pre = System.currentTimeMillis();
getHuiwen(s.toCharArray(), 0);
System.out.println(Arrays.toString(s.toCharArray()));
System.out.println(Arrays.toString(manacherIndex));
System.out.println("用时：" + (System.currentTimeMillis() - pre)+"ms");
}
private static void getHuiwen(char[] charArray, int index) {
for (int i = 0; i < charArray.length; i++) {
if (index - i >= 0 && index + i < charArray.length
&& charArray[index + i] == charArray[index - i]) {
//应该加的是直径
manacherIndex[index] = manacherIndex[index] + 2;
continue;
}
//原点的多算了一次
manacherIndex[index]--;
if (index < charArray.length - 1) {
getHuiwen(charArray, index + 1);
}
break;
}
}
Paste_Image.png
