[TOC] ## 场景 在一个字符串中是否包含另一个字符串 ## 概述 - 一句话概括,KMP算法的核心是已经匹配的字符不会重复匹配 - KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组 ### 图示   ## 解析 假设现在文本串 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 (n<m){ return -1 } next:=compute_next(needle) q:=0 for i:=0;i<n;i++ { for q>0 && 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;q<n;q++ { for k>0 && ( pattern[k]!=pattern[q]){ k=next[k-1]; } if ( pattern[k]==pattern[q]){ k++; } next[q]=k; } return next } ```