KMP 算法

最后更新于:2022-04-02 04:22:48

[TOC] ## 场景 在一个字符串中是否包含另一个字符串 ## 概述 - 一句话概括,KMP算法的核心是已经匹配的字符不会重复匹配 - KMP算法的核心,是一个被称为部分匹配表(Partial Match Table)的数组 ### 图示 ![](https://pic.leetcode-cn.com/023ce6af45af247b3c140ca0ebc0ac6d93b1fa081a1ae0fa9e1a83d790eabee0-file_1568963023074) ![](https://pic.leetcode-cn.com/8e02ee035c94ce3f8897c9f0a15e3b4c8e029a0b8b6e9ab0c3189528089c3742-file_1568963023090) ## 解析 假设现在文本串 S 匹配到 i 位置,模式串 P 匹配到 j 位置 * 如果 j = -1,或者当前字符匹配成功(即 S\[i\] == P\[j\]),都令 i++,j++,继续匹配下一个字符; * 如果 j != -1,且当前字符匹配失败(即 S\[i\] != P\[j\]),则令 i 不变,j = next\[j\]。此举意味着失配时,模式串 P 相对于文本串 S 向右移动了 j - next \[j\] 位。 * 换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的 next 值,即**移动的实际位数为:j - next\[j\]** * 如果 next [j] 等于 0 或 -1,则跳到模式串的开头字符,若 next [j] = k 且 k > 0,代表下次匹配跳到 j 之前的某个字符 思路 1.构造next数组(初始化->处理前后缀不相同的情况->处理前后缀相同的情况) 2.使用next数组来做匹配 golang 实现 ``` func strStr(haystack string, needle string) int { n:=len(haystack) m:=len(needle) if (m==0){ return 0 } if (n0 && haystack[i]!=needle[q]{ q=next[q-1] } if ( haystack[i]==needle[q]){ q++ } if (q==m){ return i+1-m; } } return -1 } func compute_next( pattern string) []int { n:=len(pattern) next:=make([]int,n) k:=0 for q:=1;q0 && ( pattern[k]!=pattern[q]){ k=next[k-1]; } if ( pattern[k]==pattern[q]){ k++; } next[q]=k; } return next } ```
';