文档介绍：字符串匹配定义:文本是一个长度为n的数组T[1…n], 模式是以个长度m<=n的数组P[1…m]
P和T的元素都是有限字母表∑中的字符
也就是蛮力匹配,每次移动一个步长,然后匹配,时间复杂度O((n-m+1)m)
-Karp算法
Rabin-Karp算法的思想是将模式串P表达为一个值,这样每次进行串匹配的时候,只需要比较这个值就可以了,而不需要对m个字符串进行m次比较。
核心思想是用一个值来代替整个字符串来参与比较
比如以十进制为例,文本串为'1234567',模式串为'234'(其值为234),当搜索指针指向第一个字符'1'时,计算出串'123'的值为123,直接与模式串的值234进行比较,不匹配,那么就表明此时模式串匹配失败,将搜索指针移向下一个字符。
如何用值来代表字符串?
想象一下将字符串转换为数值的情形
计算串"123"的值:1*100+2*10+3*1 = 123
    串"6789"的值:6*1000+7*100+8*10+9*1 = 6789
                 
十进制字母表只有0-9,因此选取基数10可以完成的表述整个串
对于Ascii字母表,则可以选取基256。
因此,将一个串表述成一个值是可行的,其时间复杂度为O(m),其中m为串的长度。
对于文本串T[1…n],可以在O(m)的时间复杂度计算出前m个字符T[1…m]的值。
而T[2…m+1],T[3…m+2],...T[n-m+1…n]的值,可以在O(n-m)的时间计算出来(动态规划)。
新的问题:值太大,溢出?
通过一个值来表述一个串以后,如果串比较长,那么这个表述串的这个值自然会比较大,而且,可能会溢出。很自然的解决办法是对这个值取模,将它限制到一个固定的范围内。
那么问题又来了,模运算是多对一映射,比如,55和66对11取模后都是0,但是它们的值并不相等。
因此,取模运算会导致一个新的问题,就是伪命中。也就是,模运算匹配,但串本身并不匹配。
可以显式的检查T[i…m+i]与P[1…m]是否相等。
假设计算的值对q取模,倘若q够大,那么T[i…m+i]的值与P[1…m]的值发生伪命中的几率就会比较低,那么额外的测试时间就足够低了。
这样看来,对字符串求值,通过值来进行串的匹配,更像一个启发式的思想,对文本串进行一次过滤,然后在进行逐字匹配。
由于每次在判定模式串是否匹配时,只需要进行一次比较,因此匹配过程中的期望时间复杂度为O(n-m+1),这个时间没有加上对模式串求值的时间O(m)。最坏是时间复杂度也为O((n-m+1)m),也就是每一次唯一产生的值都与串的值取模相等,但实际情况下比蛮力匹配要快许多。
针对模式串,构造一个有穷自动机,那么,有穷自动机接收的语言就是该模式串匹配的句子。
对于每个模式串,都存在一个字符串匹配自动机,必须在预处理阶段,根据模式构造出相应的自动机后,才能利用它来搜索字符串。构造自动机的核心是构造其状态转移函数。
这种方法功能比较强大,因为它可以搜索以正则式表达的模式串。而其他算法则不能。
先看一个例子。b,模式P为ababaca
。
如图所示。此时,红色的5个字符ababa已经匹配,
从字符c开始不匹配。