我想找到字符串 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 来解决这个问题,你能告诉我怎么做吗?
最佳答案
参见 http://homepage.usask.ca/~ctl271/810/approximate_matching.shtml其中基于后缀树的算法被推导出来在 O(kn) 时间内在长度为 n 的字符串中找到长度为 m 的模式 P 和 k 个通配符的所有出现,对于 k << m 可以比朴素的 O 好得多(nm) 时间,通过检查所有长度为 m 的子串进行匹配来实现。
关于string - KMP 修改 - 在字符串中搜索简单模板匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22968349/