当字母表由 5 个符号 {a, b, c, d, #} 组成时，我试图解决一个精确的模式匹配问题，其中特殊符号 # 匹配任何符号（包括它自己）。
例如，如果 T = ab#aca#ab#a 和 P = da#ac 则 P 从 T 中的位置 3 开始出现。我试图找到一个 O(nlogn) 时间算法来确定长度为 n 的模式 P出现在长度为 2n 的文本 T 中，假设 # 符号在 T 和 P 中出现（可能 O(n) 次）。
关于如何用卷积解决它的任何建议？
user103021
问问题
6035 次
3 回答
7
如前所述，我认为您可以处理任意字母大小的问题，但要取决于浮点精度。对于 n 个字符的字母表，将文本字符映射到（复）第 n 个单位根。对于模式字符，将 # 映射为 0，并将普通字符映射到相应文本字符的乘法逆元，以及 n 次单位根。
然后，您可以使用卷积定理在每个点上计算出从该点开始的文本与模式的点积。如果文本和模式匹配，则产品的每个组件都是 0（通配符）或 1，来自 r*r^-1，因此如果匹配，结果将为 m，其中 m 是数字模式中的非通配符。如果不匹配，则点积的所有分量并非都是 1。将这些复数视为二维向量，这些向量与表示 1 的向量的点积将小于 m，所以不匹配不会导致结果 m 并且看起来像匹配。
我注意到，如果将文本划分为模式长度的几倍的缓冲区，则可以合理有效地使用该长度的 FFT，因此复杂度不是 n log n，其中 n 是文本的长度被搜索，但 n log m，其中 m 是模式的长度。尽管如此，在我相信这是一种有竞争力的方法之前，我需要查看基准时间，即使与天真的搜索相比也是如此。
于 2011-10-24T18:18:17.550 回答
0
BNDM 算法可以处理通配符，正如这个实现所示，并且在一般情况下满足您的速度要求。但是，它具有 O(nm) 最坏情况复杂度。
为什么你在这里需要卷积？
于 2011-10-24T08:24:38.797 回答