c++ - 使用通配符生成 Knuth–Morris–Pratt 前缀表

Question

我正在实现支持通配符的 KMP 字节模式搜索。下面是生成前缀表的算法 WITHOUT 通配符:

    vector<int> PrefixFunction(string S) 
    {
        vector<int> p(S.size());
        int j = 0;
        for (int i = 1; i < (int)S.size(); i++) 
        {
            while (j > 0 && S[j] != S[i])
                j = p[j-1];

           if (S[j] == S[i])
                j++;
           p[i] = j;
        }   
        return p;
   }

上述算法的问题在于它不适用于通配符。长话短说，请考虑以下数学方程式:

1. ∵a = b
2. ∵b = c
3. ∴a = c

当不涉及通配符时，这些等式是 100% 正确的。但是，它们不适用于通配符。例如:a = 1 , b = ?? (?? 是通配符)和 c = 2 . a equals b和 b equals c ，但是 a does not equal to c

由于通配符这个奇怪的特性，上面提到的算法将无法工作!因此，我必须为通配符实现一个特定的算法。我当前的实现如下所示:

vector<int> GeneratePrefixTable(vector<int> bytes, vector<unsigned char> flags)
{
    vector<int> prefixTable(bytes.size());
    prefixTable[0] = 0;
    for (int j = 1, m = bytes.size(); j < m; j++)
    {
        int largest = 0;
        for (int i = 1; i < j; i++)
        {
            bool match = true;
            for (int k = 0; k < i; k++)
            {
                if (bytes[k] != bytes[j - i + k + 1] && !flags[k] && !flags[j - i + k + 1])
                {
                    //if the bytes do not match and neither of them is a wildcard
                    match = false;
                    break;
                }
            }
            if (!match)
            {
                continue;
            }
            largest = i;
        }

        prefixTable[j] = largest;
    }
    return prefixTable;
}

变量定义:

1. vector<int> bytes模式。又名针。
2. vector<unsigned char> flags flag 数组，表示某个位置的字节是否为通配符
3. j我们正在查看生成前缀的模式的索引#
4. largestOne目前找到的最大前缀长度
5. i我们正在测试的前缀长度

请注意，一旦发现无效前缀长度，我并没有停止搜索。这也是由于通配符的奇怪属性。例如，考虑模式 01 02 ?? 02 00 :

1. 长度为 1:前缀:1后缀:0 , 不匹配
2. 长度为 2:前缀:1 2后缀:2 0不匹配
3. 长度为 3:前缀 1 2 ??后缀:?? 2 0一场比赛!

由于这个奇怪的属性，我必须测试每个可能的前缀长度。这进一步减慢了我的算法。有哪些算法和实现方面的方法可以加快我的前缀表生成算法？

Answer 1

您混淆了两种类型。 “字符”类型比“搜索模式、字符或通配符”类型少一个元素。

这会导致您错误地认为“a”匹配“??” (通配符)。它没有。模式“a”匹配字符“a”，模式“??”匹配任何字符。明显不同的模式。

它有助于考虑正则表达式模式。 [ab] 与 [ba] 的模式相同； [0-9] 与 [0123456789] 是相同的模式，但 a 绝对不是与 相同的模式。.

模式是传递相等的。同样，使用正则表达式样式:[abc] = [acb] = [bca]。

KMP 要求您注意区分。给定当前匹配位置和匹配的前缀长度，您需要确定下一个可能的匹配位置是什么。这不涉及模式平等。它涉及模式的交集。

小回避:一个模式定义了一组要被接受的字符串。可以说两个模式有一个交集，这是一个都接受的字符串集合。对于复杂的模式，这很难计算。

实际上，KMP 将找到的搜索前缀与搜索词的移位版本进行比较。存储的值是两个模式具有非空交集的最小移位。