Why/how 最长正确 Prefix/Suffix 算法是否有效？

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

我。即，s 的每个子串最长 prefix/suffix 的长度，直到 i。您可能会猜到它是如何从算法的其余部分生成的。现在，如果 i 之后的下一个字符与 j、

之后的下一个字符不匹配

a b a b x x a b a b a ...
        ^           ^
        j           i

我们不必重试匹配，因为我们知道 最长的 prefix/suffix 我们之前的 prefix/suffix！查找 arr[j - 1] 得到 2 - 所以我们基本上缓存了此处突出显示的部分的信息

A B a b x x a b A B a ...
=== ^           === ^
    j               i

完全相同，无需再比较！

Answer 2

  *Here's one more solution*
  int length=str.length();
  int mid=length/2;
  if(length<2){
       System.out.println("-1");
  }
  for(int i=mid;i>=0;i--){
      String prefix=str.substring(0,i);
      String suffix=str.substring(length-i,length);
      if(suffix.equals("") || prefix.equals("")){
            System.out.println("-1");
      }
      if(suffix.equals(prefix)){
          System.out.println(suffix.length());
          break;
      }
      
  }

Why/how 最长正确 Prefix/Suffix 算法是否有效？

Why/how does the Longest Proper Prefix/Suffix algorithm work?

arrays

algorithm

prefix

suffix

knuth-morris-pratt