string - KMP 修改 - 在字符串中搜索简单模板匹配

Question

我想找到字符串 S 中与正则表达式 R 匹配的所有子字符串。正则表达式只能包含“.”和符号(其中“.”表示任何符号)。我正在尝试使用 KMP 来解决这个问题:

1) 构建字符串 T = R + '#' + S(这里 '#' 是分隔符)

2) 计算前缀函数。对于 T

3) 对于 pi (prefix-func. of T) 检查 '#' 之后的位置，其中 pi[i] == len(S)。在这些位置寻找子串结束。

但是前缀函数。将无法在带有“.”的字符串上正常工作我的前缀函数代码:

pi[0] = 0;
for (int j = 0, i = 1; i < R.length(); i++) {
    while (j > 0 && s[i] != s[j] && s[i] != '.' && s[j] != '.' || s[i] == '#' || s[j] == '#')
        j = pi[j - 1];
        if (s[i] == s[j] || (s[i] == '.' && s[i] != '#') || (s[j] == '.' && s[j] != '#'))
            j++;
        pi[i] = j;
}

它在测试 S="abab", T="a."时失败。

我知道可以使用 KMP 来解决这个问题，你能告诉我怎么做吗？

Answer 1

参见 http://homepage.usask.ca/~ctl271/810/approximate_matching.shtml其中基于后缀树的算法被推导出来在 O(kn) 时间内在长度为 n 的字符串中找到长度为 m 的模式 P 和 k 个通配符的所有出现，对于 k << m 可以比朴素的 O 好得多(nm) 时间，通过检查所有长度为 m 的子串进行匹配来实现。