如何用卷积解决精确模式匹配问题

Question

当字母表由5个符号{a,b,c,d,#}组成时,我试图解决精确的模式匹配问题,其中特殊符号#匹配任何符号(包括其自身).

例如,如果T = ab#aca#ab#a和P = da#ac则P从T中的位置3开始.我试图找到O(nlogn)时间算法来确定长度为n的模式P假设在T和P中出现#符号(可能是O(n)次),则发生在长度为2n的文本T中.

关于如何用卷积解决它的任何建议？

Answer 1

我认为你可以处理问题,如上所述,任意字母大小,受浮点精度的影响.对于n个字符的字母表,将文本字符映射到(复数)n个统一的根.对于模式字符,将#映射到0,并将普通字符映射到相应文本字符的乘法逆,以及统一的第n个根.

然后,您使用卷积定理在每个点处计算出该点上的文本与模式的点积.如果文本和模式匹配,产品的每个组件都是0(在外卡)或1,从r*r ^ -1,所以如果你有匹配,结果将是m,其中m是数字模式中的非通配符字符.如果没有匹配,那么点积的所有组件都不会是1.将这些复数视为二维向量,这些向量与向量表示1的点积将小于m,所以不匹配不会导致结果m并且看起来像匹配.

我注意到,如果将文本划分为模式长度的几倍的缓冲区,则可以合理有效地使用该长度的FFT,因此复杂度不是n log n,其中n是文本的长度被搜索,但是n log m,其中m是模式的长度.尽管如此,在我相信这是一种竞争方法之前,我需要看到基准时间,甚至与天真的搜索相比.