KMP算法
简介
一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人设计的线性时间字符串匹配算法。该算法主要解决的就是字符串匹配的问题。
本文参考前缀函数与KMP算法-oi.wiki
例题
LeetCode 28：找出字符串种第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
如果 needle 不是 haystack 的一部分，则返回 -1 。
1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
前置知识
- 字符串前缀
假设有一个字符串 s[0...i] (下标为0 - i)
它的前缀就定义为 s[0...j] (j <= i)，当 j < i 时，就定义为该字符串的真前缀 - 字符串后缀
同理
后缀定义为 s[j...i] (j >= 0), 当 j > 0 时，就定义为该字符串的真后缀
前缀函数 next[] 数组
next数组是KMP的核心
定义
给定一个长度为 n 的字符串 s，其 前缀函数 被定义为一个长度为 n 的数组 next。 其中 next[i] 的定义是：
如果子串 s[0...i] 有一对相等的真前缀与真后缀：s[ 0...k-1 ] 和 s[ i-(k-1)...i ] ( k-1 < i-(k-1) )，那么 next[i] 的值就是这个字符串最长的真前后缀（因为相等的真前后缀可能不止一对，所以需要的是最长的真前后缀）的长度，也就是 next[i] = k；
next[i] = max(k,max) //条件：([0...k-1] == s[i-(k-1)...i])
初始化 next[0] = 0
举例
对于字符串: a b a b a b a c
next 数组：[ 0,0,1,2,1,2,3,0 ] => "","","a","ab","a","ab","aba",""
暴力求解 next 数组
给定字符串 s
暴力求解：
双指针遍历 s，设双指针 i 为当前 s[0...i] 的前缀和的下标（截至下标），j 为遍历 0 - i 的下标（遍历匹配 s[j] 和 s[i-j]）
假设字符串 s[0...i] => j 遍历 比较 s[0] == s[i] ... s[1] == s[i-1] ... s[j] == s[i-j] (需要满足要求 j < i-j )
代码如下（Java）：
public static int[] prefixFunction(String str){
int[] next = new int[str.length()];
// next[0] = 0; // 可以省略，默认为 0
for(int i = 1; i < str.length(); i++){
for(int j = 0; j < i; j++){
// 截取 str[0...j] 和 str[i-j...i] 比较
if(i-j > j && str.substring(0,j+1).equals(str.substring(i-j,i+1))){
next[i] = j+1;
}
}
}
return next;
}
时间复杂度 O(n^3) 不推荐使用