zcmimi's blog

普通的单模式串匹配

给定模式串A(|A|=m)、文本串B(|B|=n),需要求出所有位置p,满足B串从第p个字符开始的连续m个字符,与A串完全相同

定义匹配函数C(x,y)=[A(x)-B(y)]^2,若A的第x个字符与B的第y个字符匹配,那么C(x,y)=0

再定义完全匹配函数\displaystyle P(x)=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2,若P(x)=0,则称B以第x位结束的连续m位,与A完全匹配

咋一看似乎没有什么优化方法

我们翻转A串得到S

那么

\displaystyle \begin{aligned} P(x) &=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2\\ &=\sum_{i=0}^{m-1}[S(m-i+1)-B(x-m+i+1)]^2\\ &=\sum_{i=0}^{m-1}[S(m-i+1)^2+B(x-m+i+1)^2-2S(m-i+1)B(x-m+i+1)]\\ &=\sum_{i=0}^{m-1}S(m-i+1)^2+\sum_{i=0}^{m-1}B(x-m+i+1)^2-\sum_{i=0}^{m-1}2S(m-i+1)B(x-m+i+1)] \end{aligned}

第一项是定值,第二项可以预处理前缀和解决,第三项可以卷积

\displaystyle \sum_{i=0}^{m-1}2S(m-i+1)B(x-m+i+1)]=\sum_{i+j=x}2S(i)B(j)

T=\sum_{i=0}^{m-1} S(i)^2,f(x)=\sum_{i=0}^x B(i)^2,g(x)=\sum_{i+j=x}2S(i)B(j)

那么P(x)=T+f(x)-f(x-m)-2g(x)

这样可以O(n)得到所有P(x)的值

带通配符的单模式串匹配

设通配符的数值为0,定义匹配函数C(x,y)=[A(x)-B(y)]^2A(x)B(y),那么\displaystyle P(x)=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)

按照套路,翻转A串得到S串:

\displaystyle \begin{aligned} P(x) &=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)\\ &=\sum_{i=0}^{m-1}[S(m-i+1)-B(x-m+i+1)]^2S(m-i+1)B(x-m+i+1)\\ &=\sum_{i=0}^{m-1}S(m-i+1)^3B(x-m+i+1)+\\ &\quad\sum_{i=0}^{m-1}B(x-m+i+1)^3S(m-i+1)-\\ &\quad2\sum_{i=0}^{m-1}S(m-i+1)^2B(x-m+i+1)^2 \end{aligned}

写为卷积形式:

\displaystyle P(x)=\sum_{i+j=x}S(i)^3B(j)+S(i)B(j)^3-2S(i)^2B(j)^2

fft与字符串匹配
comment评论
Search
search