[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 } ```