为什么/最长的正确前缀/后缀算法如何工作？

Question

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]为什么起作用？还是我们为什么要这样做？ 我们如何验证此步骤的正确性？

请帮助！

Answer 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

i。 e，即直到i为止s的每个子串的最长前缀/后缀的长度。您可能会猜出其余算法是如何产生的。现在，如果i之后的下一个字符与j之后的下一个字符不匹配，则>

a b a b x x a b a b a ...
        ^           ^
        j           i
我们不必重试匹配，因为我们知道最长前缀/后缀of

我们先前的前缀/后缀！查找arr[j - 1]会产生2 –因此，我们基本上缓存了此处突出显示的信息。

A B a b x x a b A B a ...
=== ^           === ^
    j               i
是相同的，不需要再次进行比较！