为什么/最长正确前缀/后缀算法如何工作? [英] Why/How does the Longest Proper Prefix/Suffix algorithm work?
问题描述
LPS(最长适当前缀,也是后缀)算法如下:
The LPS (Longest Proper Prefix which is also a Suffix) algorithm goes as follows:
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
部分还不清楚.我们为什么这样做:
The if (s.charAt(i) == s.charAt(j))
part looks clear, but the else
part is unclear.
Why do we do:
if (j != 0) {
j = arr[j - 1];
} else {
i++;
}
更具体地说,为什么 j = arr [j-1]
起作用?还是我们为什么要这样做?我们如何验证此步骤的正确性?
More specifically, why does j = arr[j - 1]
work ? Or why do we even do it? How do we validate the correctness of this step?
请帮助!
推荐答案
假设我们正在解析一个字符数组,其中 i
和 j
的位置如下:>
Let's say we are parsing an array of characters with i
and j
positioned like this:
a b a b x x a b a b ...
^ ^
j i
按住 arr
的
:
0 0 1 2 0 0 1 2 3 4
i.例如,s的每个子串的最长前缀/后缀的长度,直到 i
.您可能会猜出其余算法是如何产生的.现在,如果 i
之后的下一个字符与 j
之后的下一个字符不匹配,则
i. e., the length of the longest prefix/suffix of each substring of s of that length until i
. You can probably guess how that was generated from the rest of the algorithm. Now, if the next character after i
does not match the next character after j
,
a b a b x x a b a b a ...
^ ^
j i
我们不必重试匹配,因为我们知道我们先前的前缀/后缀的最长前缀/后缀!查找 arr [j-1]
会产生2–因此我们基本上缓存了此处突出显示的信息
we don't have to retry the matching, because we know the longest prefix/suffix of our previous prefix/suffix! Looking up arr[j - 1]
yields 2 – so we essentially cached the information that the parts highlighted here
A B a b x x a b A B a ...
=== ^ === ^
j i
完全相同,不需要再次进行比较!
are identical, and don't need to be compared again!
这篇关于为什么/最长正确前缀/后缀算法如何工作?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!