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

本文介绍了为什么/最长正确前缀/后缀算法如何工作?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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!