kmp与数电中的模式串识别

random thoughts,随便写写

前段时间学习了数电。讲用Flip-Flop做sequence detector的时候感觉和kmp很像。

KMP

这个不细说了。把暑假集训的题解抄过来了。

暴力的字符串匹配，txt字符串现在从第i为开始和pat串比较，发生失配，i变成i+1。在失配的时候从txt的i+1和pat重新比较。

发现如果pat串在某个位置失配了，前面的一定都匹配上了，考虑pat已经匹配的这一部分，如果他后面一部分和开头是一样的，那么这一部分就不需要在比较了。

比如pat: abxxxxxabxxxx这里如果到第二个b后面失配了，至少这个ab是可以重复利用的。于是发现就是要找出pat串每个位置的前缀函数是多少。如果前缀函数是p[i]，那么如果第i位发生失配了(此时txt比较到了第k位)，直接比较pat[p[i-1]]和 txt[k]就行了。如果前缀函数是0或者第i位匹配上了，才把k+1；

简单看看匹配的时候的复杂度。下面txt长度是n,pat长度是m。匹配的时候要比较n+失配次数次。可以想到一个最坏情况

pat:aaaaa
txt:aaaabaaaabaaaab

这样一来失配次数就是次，也是的，因此匹配过程就是的。然后问题在于如何求前缀函数。这可以递推计算。 1. 如果s[i]==s[p[i-1]]那么p[i]=p[i-1]+1 2. 如果s[i]!=s[p[i-1]]，这时实际上相当于这个字符串的一个后缀和一个前缀进行字符串匹配，然后最后一位失配了。用和上面类似的思想，就要找这个前缀的最后一位的前缀函数对应的字符来和第i位的字符比较。很容易写出求前缀函数的过程。

for(int i=1;i<pat.length();i++)
{
    int k=pi[i-1];
    while(k>0&&pat[i]!=pat[k])  k=pi[k-1];
    if(pat[k]==pat[i])  k++;
    pi[i]=k;
    if(pi[i]==n)    ans++;
}

前缀函数其实是和模式串每个位置对应有限状态自动机。用前缀函数描述的kmp看起来不是很直接。在Robert Sedgewick的算法第四版中描述的KMP的dfa[][]数组就很好的描述了这一点。实际上跳到前缀函数再比较一次就是使用dfa数组的KMP了。

sequence detector

用触发器设计序列检测器，检测输入的01串中的模式串。

大概方法也是根据模式串确定状态，然后构建自动机，化简状态；

思考如果检测的不只是01串，而是普通字符串。画出的状态图就会和KMP中的有限状态自动机一致。

构建和化简状态的过程实际上就是在计算前缀函数（或者说dfa[][]数组）

像KMP一样，这样的序列检测器检测模式串也只需要的时间（无论是否要求匹配overlap）

最后，感觉数电里很多东西与各种算法很接近。比如找compatible state的时候要找最大团之类的。