05 August 2008
最长的既是前缀又是后缀的子字符串
O(N^2)直接找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public String longestPrefix(String s) {
int n = s.length();
if (n < 2) return "";
char[] str = s.toCharArray();
int i = 0, j = 0;
for (j = n-2; j>=0; j--){
for (i=j; i>=0; i--){
if (str[i] != str[n-1-(j-i)]) break;
}
if (i == -1) return s.substring(0, j+1);
}
return "";
}
}
KMP, both O(n) - https://www.youtube.com/watch?v=GTJr8OvyEVQ
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public String longestPrefix(String s) {
int n = s.length();
int[] lps = new int[n];
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && s.charAt(i) != s.charAt(j)) j = lps[j-1];
if (s.charAt(i) == s.charAt(j)) lps[i] = ++j;
}
return s.substring(0, lps[n-1]);
}
}