Skip to content

Commit 770b179

Browse files
dairongpengdairongpeng
committed
manacher +
1 parent cecb9d6 commit 770b179

File tree

1 file changed

+125
-127
lines changed

1 file changed

+125
-127
lines changed

‎16-《进阶》Manacher(马拉车)算法.md

Lines changed: 125 additions & 127 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,9 @@ Manacher算法解决在一个字符串中最长回文子串的大小，例如"ab
1313

1414
## 1.2 字符串最长回文子串暴力解
1515

16-
遍历str，以i为回文对称的回文串有多长，在i位置左右扩展。所以字符串"abc123df"
16+
> 扩散法
17+
18+
遍历str，以i为回文对称的回文串有多长，在i位置左右扩展。如果字符串"abc123df"
1719

1820
i为0的时候，回文串为"a"，长度为1;
1921

@@ -42,7 +44,7 @@ i为8的时候，回文串为"#1#2#1#1#2#1#"，长度为13;
4244
复杂度最差情况是，所有字符长度为n,且所有字符都相等。经过我们的填充，字符串规模扩展到2n+1。每次寻找，都会寻找到左边界或者右边界，该方法的事件复杂度为O(N*N)
4345

4446

45-
Manacher算法解决该类问题，O(N)复杂度！
47+
Manacher算法解该类问题，O(N)复杂度可以解决
4648

4749
## 1.3 Manacher解决最长回文串O(N)
4850

@@ -63,114 +65,90 @@ Manacher算法的核心概念就是，回文半径数组pArr[],回文最右边
6365
在遍历填充数组时，会出现i在R外，和i在R内两种情况。
6466

6567

66-
当i在R外时，没有任何优化，继续遍历去寻找。当i在R内涉及到Manacher算法的优化。i在R内的时候，i肯定大于C,我们可以根据R和C求出左边界L,也可以根据i和C求出以C堆成的i'。
68+
当i在R外时，没有任何优化，继续遍历去寻找。当i在R内涉及到Manacher算法的优化。i在R内的时候，i肯定大于C,我们可以根据R和C求出左边界L,也可以根据i和C求出以C对称的i'。
6769

68-
- 情况1：i'的回文区域在彻底在L和R的内部。i不需要再求回文串，i的回文串的大小等于pArr[]中i'位置的长度。原因是i和i'关于C对称，整体在R和L范围内，R和L也是关于C对称，传递得到。O(1)
70+
- 情况1：i'的回文区域在L和R的内部。i不需要再求回文串，i的回文串的大小等于pArr[]中i'位置的长度。原因是i和i'关于C对称，整体在R和L范围内，R和L也是关于C对称，传递得到。O(1)
6971

7072

71-
- 情况2：i'的回文区域的左边界在L的左侧。i的回文半径就是i位置到R位置的长度。原因是，L以i'为堆成的L'，R以i为堆成的R'一定在L到R的范围内。且L'到L和R'到R互为回文。所以i区域的回文区域的回文半径至少为i到R的距离。由于以C为对称，得到区域为L到R,L不等于R，此处画图根据传递得到i的回文半径就是i位置到R位置的长度。O(1)
73+
- 情况2：i'的回文区域的左边界在L的左侧。i的回文半径就是i位置到R位置的长度。原因是，L以i'为对称的L'，R以i为堆成的R'一定在L到R的范围内。且L'到L和R'到R互为回文。所以i区域的回文区域的回文半径至少为i到R的距离。由于以C为对称，得到区域为L到R,L不等于R，此处画图根据传递得到i的回文半径就是i位置到R位置的长度。O(1)
7274

7375

74-
- 情况3：i'的回文区域的左边界和L相等。i'的右区域一定不会再R的右侧。根据情况2，R以i堆成的R'。R和R'确定是回文，需要验证R下一个位置和R'前一个位置是否回文，这里也可以省掉R'到R之间的验证。O(N)
76+
- 情况3：i'的回文区域的左边界和L相等。i'的右区域一定不会再R的右侧。根据情况2，R以i对称的R'。R和R'确定是回文，需要验证R下一个位置和R'前一个位置是否回文，这里也可以省掉R'到R之间的验证。O(N)
7577

7678

7779
经过以上的情况，整体O(N)复杂度
7880

81+
```Go
82+
package main
7983

80-
Code:
81-
82-
```Java
83-
public class Code01_Manacher {
84+
import (
85+
"fmt"
86+
"math"
87+
)
8488

85-
public static int manacher(String s) {
86-
if (s == null || s.length() == 0) {
87-
return 0;
88-
}
89-
// "12132" -> "#1#2#1#3#2#"
90-
char[] str = manacherString(s);
91-
// 回文半径的大小
92-
int[] pArr = new int[str.length];
93-
int C = -1;
94-
// 算法流程中，R代表最右的扩成功的位置。coding：最右的扩成功位置的，再下一个位置，即失败的位置
95-
int R = -1;
96-
int max = Integer.MIN_VALUE;
97-
for (int i = 0; i < str.length; i++) {
98-
// R是第一个违规的位置，i>= R就表示i在R外
99-
// i位置扩出来的答案，i位置扩的区域，至少是多大。
100-
// 2 * C - i 就是i的对称点。
101-
// 得到各种情况下无需验的区域
102-
pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
103-
104-
// 右侧不越界，且左侧不越界，检查需不需要扩
105-
while (i + pArr[i] < str.length && i - pArr[i] > -1) {
106-
if (str[i + pArr[i]] == str[i - pArr[i]])
107-
pArr[i]++;
108-
else {
109-
break;
110-
}
111-
}
112-
//i的右边界有没有刷新之前的最右边界。R刷新C要跟着刷新
113-
if (i + pArr[i] > R) {
114-
R = i + pArr[i];
115-
C = i;
116-
}
117-
max = Math.max(max, pArr[i]);
118-
}
119-
return max - 1;
89+
// manacher 给定一个字符串，求该字符串的最长回文子串的大小
90+
func manacher(s string) int {
91+
if len(s) == 0 {
92+
return 0
12093
}
12194

122-
public static char[] manacherString(String str) {
123-
char[] charArr = str.toCharArray();
124-
char[] res = new char[str.length() * 2 + 1];
125-
int index = 0;
126-
for (int i = 0; i != res.length; i++) {
127-
res[i] = (i & 1) == 0 ? '#' : charArr[index++];
95+
// "12132" -> "#1#2#1#3#2#"
96+
str := manacherString(s)
97+
// 回文半径的大小
98+
pArr := make([]int, len(str))
99+
C := -1
100+
// 算法流程中，R代表最右的扩成功的位置。coding：最右的扩成功位置的，再下一个位置，即失败的位置
101+
R := -1
102+
max := math.MinInt
103+
for i := 0; i < len(str); i++ {
104+
// R是第一个违规的位置，i>= R就表示i在R外
105+
// i位置扩出来的答案，i位置扩的区域，至少是多大。
106+
// 2 * C - i 就是i的对称点。
107+
// 得到各种情况下无需验的区域
108+
if R > i {
109+
pArr[i] = int(math.Min(float64(pArr[2 * C - i]), float64(R - i)))
110+
} else {
111+
pArr[i] = 1
128112
}
129-
return res;
130-
}
131113

132-
// for test
133-
public static int right(String s) {
134-
if (s == null || s.length() == 0) {
135-
return 0;
136-
}
137-
char[] str = manacherString(s);
138-
int max = 0;
139-
for (int i = 0; i < str.length; i++) {
140-
int L = i - 1;
141-
int R = i + 1;
142-
while (L >= 0 && R < str.length && str[L] == str[R]) {
143-
L--;
144-
R++;
114+
// 右侧不越界，且左侧不越界，检查需不需要扩
115+
for i + pArr[i] < len(str) && i - pArr[i] > -1 {
116+
if str[i + pArr[i]] == str[i - pArr[i]] {
117+
pArr[i]++
118+
} else {
119+
break
145120
}
146-
max = Math.max(max, R - L - 1);
147121
}
148-
return max / 2;
149-
}
150122

151-
// for test
152-
public static String getRandomString(int possibilities, int size) {
153-
char[] ans = new char[(int) (Math.random() * size) + 1];
154-
for (int i = 0; i < ans.length; i++) {
155-
ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
123+
//i的右边界有没有刷新之前的最右边界。R刷新C要跟着刷新
124+
if i + pArr[i] > R {
125+
R = i + pArr[i]
126+
C = i
156127
}
157-
return String.valueOf(ans);
128+
max = int(math.Max(float64(max), float64(pArr[i])))
158129
}
159130

160-
public static void main(String[] args) {
161-
int possibilities = 5;
162-
int strSize = 20;
163-
int testTimes = 5000000;
164-
System.out.println("test begin");
165-
for (int i = 0; i < testTimes; i++) {
166-
String str = getRandomString(possibilities, strSize);
167-
if (manacher(str) != right(str)) {
168-
System.out.println("Oops!");
169-
}
131+
return max - 1
132+
}
133+
134+
func manacherString(str string) []byte {
135+
charArr := []byte(str)
136+
res := make([]byte, len(str) * 2 + 1)
137+
index := 0
138+
for i := 0; i != len(res); i++ {
139+
if (i & 1) == 0 { // 奇数位填充'#'
140+
res[i] = '#'
141+
} else {
142+
res[i] = charArr[index]
143+
index++
170144
}
171-
System.out.println("test finish");
172145
}
146+
return res
147+
}
173148

149+
func main() {
150+
s := "abc12321ef"
151+
fmt.Println(manacher(s)) // 5
174152
}
175153
```
176154

@@ -181,58 +159,78 @@ public class Code01_Manacher {
181159
> 解题思路：转化为必须包含最后一个字符的最长回文串多长？例如，"abc12321"，以最后一个1的最长回文串为"12321"，那么最少需要添加"cba"3个字符
182160
183161

184-
```Java
185-
public class Code02_AddShortestEnd {
162+
```Go
163+
package main
164+
165+
import (
166+
"fmt"
167+
"math"
168+
)
186169

187-
public static String shortestEnd(String s) {
188-
if (s == null || s.length() == 0) {
189-
return null;
170+
func shortestEnd(s string) string {
171+
if len(s) == 0 {
172+
return ""
173+
}
174+
175+
str := manacherString(s)
176+
pArr := make([]int, len(str))
177+
178+
C := -1
179+
R := -1
180+
maxContainsEnd := -1
181+
182+
for i := 0; i != len(str); i++ {
183+
if R > i {
184+
pArr[i] = int(math.Min(float64(pArr[2 * C - i]), float64(R - i)))
185+
} else {
186+
pArr[i] = 1
190187
}
191-
char[] str = manacherString(s);
192-
int[] pArr = new int[str.length];
193-
int C = -1;
194-
int R = -1;
195-
int maxContainsEnd = -1;
196-
for (int i = 0; i != str.length; i++) {
197-
pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
198-
while (i + pArr[i] < str.length && i - pArr[i] > -1) {
199-
if (str[i + pArr[i]] == str[i - pArr[i]])
200-
pArr[i]++;
201-
else {
202-
break;
203-
}
204-
}
205-
if (i + pArr[i] > R) {
206-
R = i + pArr[i];
207-
C = i;
208-
}
209-
if (R == str.length) {
210-
maxContainsEnd = pArr[i];
211-
break;
188+
189+
for i + pArr[i] < len(str) && i - pArr[i] > -1 {
190+
if str[i + pArr[i]] == str[i - pArr[i]] {
191+
pArr[i]++
192+
} else {
193+
break
212194
}
213195
}
214-
char[] res = new char[s.length() - maxContainsEnd + 1];
215-
for (int i = 0; i < res.length; i++) {
216-
res[res.length - 1 - i] = str[i * 2 + 1];
196+
197+
if i + pArr[i] > R {
198+
R = i + pArr[i]
199+
C = i
200+
}
201+
202+
if R == len(str) {
203+
maxContainsEnd = pArr[i]
204+
break
217205
}
218-
return String.valueOf(res);
219206
}
220207

221-
public static char[] manacherString(String str) {
222-
char[] charArr = str.toCharArray();
223-
char[] res = new char[str.length() * 2 + 1];
224-
int index = 0;
225-
for (int i = 0; i != res.length; i++) {
226-
res[i] = (i & 1) == 0 ? '#' : charArr[index++];
227-
}
228-
return res;
208+
res := make([]byte, len(s) - maxContainsEnd + 1)
209+
for i := 0; i < len(res); i++ {
210+
res[len(res) - 1 -i] = str[i * 2 + 1]
229211
}
230212

231-
public static void main(String[] args) {
232-
String str1 = "abcd123321";
233-
System.out.println(shortestEnd(str1));
213+
return string(res)
214+
}
215+
216+
func manacherString(str string) []byte {
217+
charArr := []byte(str)
218+
res := make([]byte, len(str) * 2 + 1)
219+
index := 0
220+
for i := 0; i != len(res); i++ {
221+
if (i & 1) == 0 { // 奇数位填充'#'
222+
res[i] = '#'
223+
} else {
224+
res[i] = charArr[index]
225+
index++
226+
}
234227
}
228+
return res
229+
}
235230

231+
func main() {
232+
s := "abcd123321"
233+
fmt.Println(shortestEnd(s)) // dcba => abcd123321dcba
236234
}
237235
```
238236

0 commit comments

Comments
 (0)