本文共 3571 字,大约阅读时间需要 11 分钟。
最长回文子串问题:给定一个字符串,求它的最长回文子串长度。
如果一个字符串正着读和反着读是一样的,那么我们称之为回文串。例如:abba、aaaa、abvcba、123321等
暴力法:遍历字符串的所有子串,对每个字串进行判断。求字符串的所有子串时间复杂度为O(n^2),判断回文后,总的时间复杂度为O(n^3)。我们规定在判断回文的时候从最长的子串开始,一旦找到就返回。判断回文的时候,采用从外到内左右成对推进方式进行。
import java.util.Scanner;public class Main { static String str = new String(); public static void main(String[] args) { Scanner in = new Scanner(System.in); str = in.next(); System.out.println(sub()); } private static int sub() { int low, high; for (int len = str.length() - 1; len > 0; len--) { for (low = 0, high = low + len; high < str.length(); low++, high++) { if (check(low, high)) { return high - low + 1; } } } return 1; } private static boolean check(int low, int high) { while (low <= high) { if (str.charAt(low) == str.charAt(high)) { low++; high--; } else { return false; } } return true; }}
从内到外逐个推进方式:由于回文串的特性,我们可以以每个位置为中心进行检查,这样可以不用暴力所有的子串,减少了重复的判断。时间复杂度为O(n^2)。这里要注意检查是要关注奇偶的不同情况,如abba和aba。
import java.util.Scanner;public class Main2 { static String str = new String(); static int max = 0; public static void main(String[] args) { Scanner in = new Scanner(System.in); str = in.next(); sub(); System.out.println(max); } private static void sub() { if (str.length() == 1) { max = 1; } for (int i = 0; i < str.length() - 1; i++) { check(i, i); check(i, i+1); } } private static void check(int low, int high) { while (low >= 0 && high < str.length()) { if (str.charAt(low) == str.charAt(high)) { if (high - low + 1 > max) { max = high - low + 1; } low--; high++; } else { return; } } }}
Manacher算法:俗称马拉车算法。这是目前求解最长回文串的最优算法。第二种思路在会将从str.charAt(0)一直检查到str.charAt(lstr.length-1),这样的话还是有许多不必要的操作,而这种算法的核心就在于优化了这一块的判断,跳过某些不必要的值。
由于回文串会出现奇数和偶数不同的情况,如abba和abcba,算法采用插入“#”的方法,使得所有的串都变成奇数串(“$”是占0的位置,从1开始方便操作),这个新的串我们命名为s_new[]。之后定义p[],用p[i]表示以s_new[i]为中心的最长回文串的半径(包含自身),如abcba的s_new["c"] = 3 (半径为2,再加自身)。我们以字符串abbabcbac为例,最长回文子串为abcba,长度为5。
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
s_new[i] | $ | # | a | # | b | # | b | # | a | # | b | # | c | # | b | # | a | # | c | # |
p[i] | 1 | 2 | 1 | 2 | 5 | 2 | 1 | 4 | 1 | 2 | 1 | 6 | 1 | 2 | 1 | 2 | 1 | 2 | 1 |
那么如何计算p[i]就成了这个算法的难点,我们自然不能按着思路二:先令p[i]=1,再以s_new[i]为中心判断两侧是否相等,p[i]++,这是非常低效的。实际上,我们可以不让p[i]初始化为1,我们设定两个变量mx和id,id为s_new[i]的下标(也就是i),mx表示以s_new[id]为中心的最长回文串的右侧边界,以abcba为例,s_new["c"] = 3,id=2("c"的下标),对应的mx=id+s_new["c"] = 5,刚好就是最右侧"a"的下标。
结合下图,对于i<mx的情况 , 存在p[i] = min(p [2*id-i], mx-i)。
解释一下上面式子,2*id-i = j,所以p[2*id - i] = p[j],即以s_new[j]为中心的最长回文串的半径(包含自身)。因为以id为中心的回文子串的长度为mx与其对称点之间的距离,而要求p[i],则可以利用p[j]来加快查找。
而之所以上面的式子成立是需要深入探讨的,有兴趣的朋友可以参考
import java.util.Scanner;public class Main { static String str = new String(); static char[] s_new; static int[] p; public static void main(String[] args) { Scanner in = new Scanner(System.in); str = in.next(); s_new = new char[str.length() * 2 + 2]; p = new int[str.length() * 2 + 2]; System.out.println(Manacher()); } private static int Manacher() { // TODO Auto-generated method stub int len = init(); int maxlen = -1; int id = 0; int mx = 0; for (int i = 1; i < len; i++) { if (i < mx) { p[i] = Math.min(p[2 * id - i], mx - i); } else { p[i] = 1; } while (i + p[i] < s_new.length && i - p[i] >= 0 &&s_new[i - p[i]] == s_new[i + p[i]]) { p[i]++; } if (mx < i + p[i]) { id = i; mx = i + p[i]; } maxlen = Math.max(maxlen, p[i] - 1); } return maxlen; } private static int init() { // TODO Auto-generated method stub s_new[0] = '$'; s_new[1] = '#'; int j = 2; for (int i = 0; i < str.length(); i++) { s_new[j++] = str.charAt(i); s_new[j++] = '#'; } return j; }}