數(shù)據(jù)結(jié)構(gòu)與算法之Manacher算法

---

目錄

Manacher算法概述

Manacher算法代碼實(shí)現(xiàn)

擴(kuò)展題——如果只能向字符串后面添加字符，怎么讓整體串變成回文串，要求填的字符最少

---

1. Manacher算法概述

Manacher算法，又叫“馬拉車(chē)”算法，可以在時(shí)間復(fù)雜度為O(n)的情況下求解一個(gè)字符串的最長(zhǎng)回文子串長(zhǎng)度的問(wèn)題。

詳細(xì)請(qǐng)見(jiàn)博客：https://www.jianshu.com/p/116aa58b7d81 ，寫(xiě)的很好，就不再?gòu)?fù)述一遍了。

---

2. Manacher算法代碼實(shí)現(xiàn)

public class Code_Manacher {public static char[] manacherString(String str) {char[] charArray = str.toCharArray();char[] res = new char[charArray.length * 2 + 1];int index = 0;for (int i = 0; i < res.length; i++) {res[i] = (i & 1) == 0 ? '#' : charArray[index++];}return res;}public static int maxLcpsLength(String str) {if (str == null || str.length() == 0) {return 0;}char[] charArr = manacherString(str);int[] pArr = new int[charArr.length]; //回文半徑int C = -1;int R = -1;int max = Integer.MIN_VALUE;for (int i = 0; i != charArr.length; i++) {//區(qū)分情況一和情況二pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1; // 情況1 ：i在R外， 暴力擴(kuò) // 情況2 ： i在R里， i'的回文在L，R內(nèi) // 情況3 ： i在R里，i'的回文在L，R外 // 情況4 ：i'回文左邊界和L壓線，從R的右邊擴(kuò)。//如果要驗(yàn)的區(qū)域沒(méi)越界，并且左邊區(qū)域也沒(méi)越界。就再擴(kuò)一下，如果是情況二和情況三，那么會(huì)失敗while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {//情況一，情況四if (charArr[i + pArr[i]] == charArr[i - pArr[i]])pArr[i]++;else {//情況二，情況三break;}}if (i + pArr[i] > R) {R = i + pArr[i];C = i;}max = Math.max(max, pArr[i]);}return max - 1;}public static void main(String[] args) {String str1 = "abc1234321ab";System.out.println(maxLcpsLength(str1));}}

編譯結(jié)果：

---

3. 擴(kuò)展題——如果只能向字符串后面添加字符，怎么讓整體串變成回文串，要求填的字符最少

代碼實(shí)現(xiàn)

public class Code_Manacher_ShortestEnd {public static char[] manacherString(String str) {char[] charArr = str.toCharArray();char[] res = new char[str.length() * 2 + 1];int index = 0;for (int i = 0; i != res.length; i++) {res[i] = (i & 1) == 0 ? '#' : charArr[index++];}return res;}public static String shortestEnd(String str) {if (str == null || str.length() == 0) {return null;}char[] charArr = manacherString(str);int[] pArr = new int[charArr.length];int index = -1;int pR = -1;int maxContainsEnd = -1;for (int i = 0; i != charArr.length; i++) {pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {if (charArr[i + pArr[i]] == charArr[i - pArr[i]])pArr[i]++;else {break;}}if (i + pArr[i] > pR) {pR = i + pArr[i];index = i;}if (pR == charArr.length) {maxContainsEnd = pArr[i];break;}}char[] res = new char[str.length() - maxContainsEnd + 1];for (int i = 0; i < res.length; i++) {res[res.length - 1 - i] = charArr[i * 2 + 1];}return String.valueOf(res);}public static void main(String[] args) {String str2 = "abcd123321";System.out.println(str2);System.out.println(shortestEnd(str2));}}

編譯結(jié)果：

超強(qiáng)干貨來(lái)襲 云風(fēng)專(zhuān)訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法之Manacher算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。