-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode0214.java
40 lines (35 loc) · 1.33 KB
/
Leetcode0214.java
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
package com.y2019.m12.d08;
import java.util.Arrays;
/**
* Created by zhangweilong on 2019/12/08
*
* @author zhangweilong@corp.netease.com
* @since 2019/12/08
*
* kmp讲解: https://blog.csdn.net/f1033774377/article/details/82556438
*/
public class Leetcode0214 {
public String shortestPalindrome(String s) {
String str = s + "$" + new StringBuilder(s).reverse();
int[] next = calNext(str);
//根据下面next数组的意义, +1才是最长前缀后追的长度
int maxLength = next[next.length - 1] + 1;
return new StringBuilder(s.substring(maxLength)).reverse().append(s).toString();
}
//f数组表示前i个字符组成的字符串, 最长相同前缀后缀长度
//为了实现方便,这里表示的是 最长相同前缀后缀长度-1
int[] calNext(String str) {
int[] f = new int[str.length()];
//F[0]=-1 (虽说这里应该是0,但为了方便判越界,同时为了方便判断第0位与第i位,程序中这里置为-1)
f[0] = -1;
for (int i = 1; i < str.length(); i++) {
int j = f[i - 1];
while (str.charAt(j + 1) != str.charAt(i) && j >= 0) {
j = f[j];
}
if (str.charAt(j + 1) == str.charAt(i)) f[i] = j + 1;
else f[i] = -1;
}
return f;
}
}