用通配符生成Knuth-Morris-Pratt前缀表

Question

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

    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标志数组以指示某个位置的字节是否为通配符
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"，模式”？“？任何字符都匹配。显然是不同的模式。

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

模式在传递上是相等的。同样，使用regex样式：[abc] = [acb] = [bca]。

KMP要求您小心区分。给定当前匹配位置和匹配前缀长度，您需要确定下一个可能的匹配位置。这不涉及模式相等。它涉及到模式的交集。

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

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