LPS(最长的专有前缀,也是后缀)算法如下:
public static int[] constructLPSArray(String s) {
int n = s.length();
int[] arr = new int[n];
int j = 0;
for (int i = 1; i < n; ) {
if (s.charAt(i) == s.charAt(j)) {
arr[i] = j + 1;
i++;
j++;
} else {
if (j != 0) {
j = arr[j - 1];
} else {
i++;
}
}
}
return arr;
}
if (s.charAt(i) == s.charAt(j))
部分看起来很清楚,但else
部分不清楚。我们为什么这样做:
if (j != 0) {
j = arr[j - 1];
} else {
i++;
}
更具体地说,为什么j = arr[j - 1]
工作 ?或者我们为什么要这样做?我们如何验证这一步的正确性?
最佳答案
假设我们正在用 i
解析一个字符数组和 j
定位如下:
a b a b x x a b a b ...
^ ^
j i
与
arr
保持:0 0 1 2 0 0 1 2 3 4
一世。即,该长度的 s 的每个子串的最长前缀/后缀的长度,直到
i
.您可能会猜到它是如何从算法的其余部分生成的。现在,如果 i
之后的下一个字符不匹配 j
之后的下一个字符,a b a b x x a b a b a ...
^ ^
j i
我们不必重试匹配,因为我们知道我们之前的前缀/后缀中最长的前缀/后缀!向上看
arr[j - 1]
产生 2 - 所以我们基本上缓存了这里突出显示的部分的信息A B a b x x a b A B a ...
=== ^ === ^
j i
完全相同,不需要再次比较!
关于arrays - 为什么/如何使用最长的正确前缀/后缀算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60853582/