数据结构-KMP算法

KMP算法 它是 在一个长字符串中匹配一个短子串的无回溯算法 定义 s 模式串 m 模式串的长度text 要匹配的字符串 n text的长度设text x1 x2 xn s a1 a2 am 则当存在i使xi k ak k 1 2 m 时 认为text与模式串匹配 当然text也可能与模式串有多处匹配例如 text abcabca s abc则text与s匹配的位置有3和6 朴素算法 枚举text中的每一个位置 判断以该位置为起始位置的长度为m的子串是否与s匹配 显然时间复杂度为O m n 伪代码如下 voidfun char text char s for i 0 text i i for j 0 j m j if text i j s j break if j m printf 匹配成功 n return printf 无法匹配 n KMP算法 作为一种无回溯的算法 它是高效的 待会儿你将看到它的时间复杂度为O m n 空间复杂度也为O m n 而且 它很容易理解 代码也很短 定义 next 为对应模式串的数组设字符串为s1s2s3 sm 其中s1 s2 s3 si sm均是字符 则next i m 当且仅当满足如下条件 字符串s1s2 smequals字符串s i m 1 si 1si并且s1s2 sms m 1 unequalss i m s i m 1 si 1si 通俗地讲 next i 保存了以s i 为结尾的后缀与模式串前缀的最长匹配数 定义 例如 s abcabcddeanext 0001230001i 5时 后缀有c bc abc cabc bcabc abcabc 相应的前缀为 a ab abc abca abcab abcabcs ababacbnext 0012300 KMP算法的运行过程 我们用两个指针i和j分别表示 A i j 1 i 与B 1 j 完全相等 也就是说 i是不断增加的 随着i的增加j相应地变化 且j满足以A i 结尾的长度为j的字符串正好匹配B串的前j个字符 j当然越大越好 现在需要检验A i 1 和B j 1 的关系 如果a i 1 b j 1 i和j各加1 什么时候j m 就说B是A的子串 B串已经整完了 KMP算法的运行过程 如果a i 1 b j 1 这时候怎么办 i 123456789 A abababaabab B ababacbj 1234567j 5时 a i 1 b j 1 我们要把j改成比它小的值j 改成多少合适呢 KMP算法的运行过程 i 123456789 A abababaabab B ababacbj 1234567记住 我们要保持A i j 1 i 与B 1 j 完全相等 因而j 是最大的数使a i j 1 i 与B 1 j 完全相等 KMP算法的运行过程 i 123456789 A abababaabab B ababacbj 1234567显然是求一个最长的以i为末尾的后缀要与B的前缀匹配 由于A i j 1 i 与B 1 j 完全相等 故令j next j 即可保证此性质保留 KMP算法的运行过程 i 123456789 A abababaabab B ababacbj 1234567i 123456789 A abababaabab B ababacbj 1234567 KMP算法的运行过程 需要注意的是i并没有动 改变的只是j的值如果改变j的值后a i 1 仍不等于b j 1 的话 继续改变j值直到a i 1 b j 1 或者j 0j 0表示i 1前面无论怎么匹配都不能使a i 1 b j 1 只好让a i 1 与b j 1 单独匹配还是上一个例子 再演示一下 KMP算法的运行过程 i 123456789 A abababaabab B ababacbj 1234567当i 6 j 5时 a i 1 b j 1 故令j next 5 3 KMP算法的运行过程 i 123456789 A abababaabab B ababacbj 1234567此时i 6 j 3仍不满足a i 1 b j 1 故继续减小j 使j next 3 1 KMP算法的运行过程 i 123456789 A abababaabab B ababacbj 1234567此时i 6 j 1仍不满足a i 1 b j 1 故继续减小j 使j next 1 0 KMP算法的运行过程 i 123456789 A abababaabab B ababacbj 1234567终于 A 8 B 1 i变为8 j为1 KMP算法的运行过程 i 123456789 A abababadbab B ababacbj 1234567事实上 有可能j到了0仍然不能满足A i 1 B j 1 比如A 8 d 时 因此 准确的说法是 当j 0了时 我们直接增加i值但忽略j直到出现A i B 1 为止 KMP代码 kmpj 0 for i 0 i0 next数组 nextmemset next 0 sizeof next for i 1 i bn i temp next i 1 while temp 时间复杂度分析 由于while循环的不确定性 好像时间复杂度很高 但事实上 我们可以看到无论是j还是temp 它只在程序的最后 1 故最多 n m 因而while循环最多 n m 因而算法的复杂度都是线性的 next的复杂度O m KMP的复杂度为O n 关于next的一个性质 问题的提出 关于next的一个性质 现在的问题是 如何快速找出S的最小循环周期 循环节 呢 Len是s的长度给出结论 如果len len next len 1 0 则字符串中必存在最小循环节 且循环次数即为len len next len 1 关于next的一个性质 证明 必要性 因为字符串中存在最小循环节 设长度为k next len 1 len k 所以len len next len 1 0 充分性 令k1 len next len 1 由于k1整除len 所以可以相应的把len划分为n片区域 n len k1 从小到大依次表示为t1 t2 tn 由next数组的定义可知 t1 t2 t2 t3 t n 1 tn 且相应的片区域即为最小 所以循环次数也为len len next len 1 关于next的一个性质 例 poj2406题意 给你一串字符串 问它的循环次数Sampleinput abcdaaaaabababSampleoutput143 核心代码如下 if n n next n 1 0 printf d n n n next n 1 elseprintf 1 n 关于next的一个性质 补充一下 S abcabcabcan next n 1 3 虽然10 3 0 但是它有理论意义 可以看到若在S后面加上bc abc就又是最小循环周期了 故这里要注意的是len next len 1 为这个串的最小循环节的长度 这不需要最后的子串是完整的 if len len next len 1 0 这个求得的是串的最大的循环的个数这个要求最后的子串是完整的 思考 KMP不仅仅是匹配完全相等的情况 其思想完全适用于对一定规律的字符进行匹配Eg http poj org problem id 3167 关于扩展KMP 了解 我们先比较一下KMP和扩展KMP所表示的意义KMP next数组的性质是模式串中每一个位置的前缀和此串其实后缀的最大匹配个数kmp匹配时的性质是求出模板串在主串中出现的位置扩展KMP next数组的性质是模板串中每一个位置的后缀和此串前缀匹配的最大个数kmp匹配的性质是主串中的每个位置和模板串的最多匹配个数 可以看到KMP匹配的是模式串的长度 显然扩展KMP是KMP的一种扩展 扩展KMP 像求KMP的next数组一样 我们先求A i 表示模式串的后缀和模式串的最长公共前缀 然后再利用A i 求出B i 说明一下A的求法 B同理现在我们要求A i 且A 1 A i 1 已经求出 设k 且1 k i 1 并满足k A k 最大所以T k T k A k 1 T 0 T A k 1 推出T i T k A k 1 T i k T A k 1 令L A i k 若L i 1 k A k 1 由A是最长公共前缀知A i L 否则 向后匹配 直到字符串失配并相应更新 扩展KMP 关于复杂度 很容易看出 在计算的过程中 凡是访问过的点 都不需要重新访问了 一旦比较 都是比较以前从不曾探访过的点开始 因此总的时间复杂度是O n m 是线性的 扩展KMP 求模板串中的a数组j 0 while T 0 j T 1 j j j 1 intA 1 j k 1 for inti 2 i m i intLen k A k 1 L A i k if L Len i 1 A i L else j max 0 Len i 1 while T i j T 0 j j j 1 A i j k i 扩展KMP 求主串中的b数组j 0 while T 0 j S 0 j j j 1 intB 0 j k 0 for inti 1 i m i intLe