string - 了解 Knuth-Morris-Pratt 算法

Question

谁可以给我解释一下这个？我一直在阅读它，但仍然很难理解。

文字：ababdbaababa
图案： ababa

ababa 的表是 -1 0 0 1 2。

我想我了解表格是如何构造的，但是，一旦发生不匹配，我不明白如何转移。好像我们在换档时甚至不使用桌子？

我们什么时候使用这张桌子？

Answer 1

在这里，我简要描述了计算前缀函数并在此处切换文本。

更多信息：Knuth–Morris–Pratt 字符串搜索算法

在文本中移动：

Text:     ABC ABCDAB ABCDABCDABDE
Pattern : ABCDABD

场景 1 - 模式和文本中有一些匹配的字符。
例如 1：这里有3 个匹配的字符。

从表中获取3 个字符的值。（索引 2，ABC）即 0 因此 shift = 3 - 0 即 3

例如 2：这里有6 个匹配的字符。

从表中获取6 个字符的值。(索引 5, ABCDAB) 即 2 因此 shift = 6 - 2 即 4

场景 2 - 如果没有匹配的字符，则移动一位。

Answer 2

发生不匹配时使用该表。让我们将模式应用于您的文本：

您开始将文本与模式匹配并测试您的模式是否可以在文本中，从第一个位置开始。你比较text[1]，pattern[1]结果证明是匹配的。你对和做同样text[2]的事情。text[3]text[4]

text[5]当你想匹配pattern[5]你没有匹配（d<> a）。然后您就知道您的模式不会从第一个位置开始。然后，您可以为位置 2 重新开始匹配，但这效率不高。您现在可以使用该表了。

错误发生在pattern[5]所以你去table[5]which is 2. 这告诉你可以在当前位置再次开始匹配 2 个已经匹配的字符。table[5]您可以从之前的位置 (1) + (2)=3开始，而不必从匹配位置 2 开始。事实上，如果我们看text[3]和text[4]，我们会发现它分别等于pattern[1]和pattern[2]。

表中的数字告诉您发生错误时已经匹配了多少位置。在这种情况下，下一个模式的 2 个字符已经匹配。然后，您可以立即开始匹配位置 3 并跳过位置 2（因为从位置 [2] 开始找不到模式）。

Answer 3

好吧，这是一个古老的话题，但希望将来搜索此内容的人会看到它。上面给出的答案很好，但我自己通过一个例子来看看到底发生了什么。

说明的第一部分取自wiki，我真正想详细说明的部分是这个回溯数组是如何构造的。

开始：

我们通过算法的（相对人为的）运行来工作，其中

W = "ABCDABD" and 
S = "ABC ABCDAB ABCDABCDABDE". 

在任何给定时间，算法都处于由两个整数确定的状态：

m它表示 S 中的位置，它是 W 的预期匹配的开始

iW 中的索引表示当前正在考虑的字符。

在每一步中，如果它们相等，我们会比较并推进S[m+i]。W[i]这在运行开始时被描述，例如

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

我们通过将 W 的连续字符与 S 的“平行”字符进行比较，如果它们匹配则从一个移动到下一个。然而，在第四步中，我们得到 S[3] 是一个空格，而 W[3] = 'D' 是一个不匹配。我们没有在 S[1] 处再次开始搜索，而是注意到除了 0 之外，在 S 中的位置 0 和 3 之间没有出现“A”；因此，在之前检查了所有这些字符之后，我们知道如果再次检查它们，就不可能找到匹配的开头。因此我们继续下一个字符，设置 m = 4 和 i = 0。

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

当在 W[6] (S[10]) 处再次出现差异时，我们很快获得了几乎完全匹配的“ABCDAB”。但是，就在当前部分比赛结束之前，我们传递了一个“AB”，这可能是新比赛的开始，所以我们必须考虑到这一点。由于我们已经知道这些字符匹配当前位置之前的两个字符，我们不需要再次检查它们；我们只需重置 m = 8, i = 2 并继续匹配当前字符。因此，我们不仅省略了 S 的先前匹配的字符，而且还省略了 W 的先前匹配的字符。

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

然而，这个搜索立即失败，因为模式仍然不包含空格，所以在第一次试验中，我们返回 W 的开头并从 S 的下一个字符开始搜索：m = 11，重置 i = 0。

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

我们再次立即找到匹配“ABCDAB”，但下一个字符“C”与单词 W 的最后一个字符“D”不匹配。像以前一样推理，我们设置 m = 15，从两个开始 -直到当前位置的字符串“AB”，设置i = 2，从当前位置继续匹配。

              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

这次我们能够完成匹配，其第一个字符是 S[15]。

上面的例子包含了算法的所有元素。目前，我们假设存在一个“部分匹配”表 T，如下所述，它指示如果当前匹配以不匹配结束，我们需要在哪里寻找新匹配的开始。T 的条目是这样构造的，如果我们从 S[m] 开始的匹配在比较 S[m + i] 和 W[i] 时失败，那么下一个可能的匹配将从索引 m + i - T[ i] 在 S 中（也就是说，T[i] 是我们在不匹配之后需要做的“回溯”的数量）。这有两个含义：首先，T[0] = -1，这表明如果 W[0] 不匹配，我们不能回溯，必须简单地检查下一个字符；其次，尽管下一个可能的匹配将从索引 m + i - T[i] 开始，如上例所示，

回溯阵列构造：

所以这个回溯数组 T[] 我们将调用 lps[]，让我们看看我们如何计算这个家伙

lps[i] = the longest proper prefix of pat[0..i] 
            which is also a suffix of pat[0..i].

示例：对于模式“AABAACAABAA”，

lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

//所以只是通过这个真正的快速

 lps[0] is just 0 by default
 lps[1] is 1 because it's looking at AA and A is both a prefix and suffix
 lps[2] is 0 because it's looking at AAB and suffix is B but there is no prefix equal to B unless you count B itself which I guess is against the rules
 lps[3] is 1 because it's looking at AABA and first A matches last A
 lps[4] is 2 becuase it's looking at AABAA and first 2 A matches last 2 A
 lps[5] is 0 becuase it's looking at AABAAC and nothing matches C
 ...


 For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]
 For the pattern “AAAAA”, lps[] is [0, 1, 2, 3, 4]
 For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
 For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

如果您考虑一下，这完全是有道理的...如果您不匹配，显然您想尽可能回溯，回溯多远（后缀部分）本质上是前缀，因为您必须从匹配开始根据定义再次出现第一个字符。所以如果你的字符串看起来像

aaaaaaaaaaaaaaa..b..aaaaaaaaaaaaaaac并且你在最后一个字符 c 上不匹配，然后你想重用aaaaaaaaaaaaaaa作为你的新头，仔细考虑一下

Answer 4

使用 Java 的完整解决方案：

package src.com.recursion;
/*
 * This Expains the Search of pattern in text in O(n)
 */
public class FindPatternInText {
    public int checkIfExists(char[] text, char[] pattern) {
        int index = 0;
        int[] lps = new int[pattern.length];
        createPrefixSuffixArray(pattern, lps);
        int i = 0;
        int j = 0;
        int textLength = text.length;
        while (i < textLength) {
            if (pattern[j] == text[i]) {
                j++;
                i++;
            }
            if (j == pattern.length)
                return i - j;
            else if (i < textLength && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return index;
    }

    private void createPrefixSuffixArray(char[] pattern, int[] lps) {
        lps[0] = 0;
        int index = 0;
        int i = 1;
        while (i < pattern.length) {
            if (pattern[i] == pattern[index]) {
                lps[i] = index;
                i++;
                index++;
            } else {
                if (index != 0) {
                    index = lps[index - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }
    public static void main(String args[]) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        System.out.println("Point where the pattern match starts is "
                + new FindPatternInText().checkIfExists(text.toCharArray(), pattern.toCharArray()));
    }
}