0

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

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

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

3) 对于 pi（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 来解决这个问题，你能告诉我怎么做吗？

4

2 回答 2

1

请参阅http://homepage.usask.ca/~ctl271/810/approximate_matching.shtml，其中派生了基于后缀树的算法，以在长度为 n 的字符串中查找长度为 m 且带有 k 个通配符的模式 P 的所有出现O(kn) 时间，对于 k << m 而言，这比通过检查所有长度为 m 的子串是否匹配来实现的朴素 O(nm) 时间要好得多。

于 2014-04-09T19:41:08.753 回答
0

我不知道处理无关符号的 KMP 修改。您可以改为构建确定性字符串匹配自动机，或者可能在连续的非无关符号上使用 Aho-Corasick 变体。我不知道如何证明对其中任何一个的良好最坏情况限制。

来自 SODA 2002的 Adam Kalai 的单页纸讨论了一种非常简单的基于 FFT 的方法来解决这个问题。如果最坏情况的复杂性很重要，我可能会建议使用它。

于 2014-04-09T17:30:15.087 回答