KMP算法解决的问题:在字符串(主串)中是否能够定位出模式串(子串)。
上面提及到暴力匹配字符串,为什么不使用呢?时间复杂度O(m*n),而KMP算法时间复杂度为O(m+n)。...第一位依次与其余字符组成的字符串集合;
后缀:除第一位以外最后一位依次与其余字符组成的字符串集合;
简单举例:
字符串ABCD,其前缀:A,AB,ABC; 后缀:BCD,CD,D
部分匹配值:子串的前缀和后缀共有元素的长度...简单举例:列举字符串ABCDABD的各个子串公共元素长度如下:
- "A"的前缀和后缀都为空集,共有元素的长度为0;
- "AB"的前缀为[A],后缀为[B],共有元素的长度为0;
...- "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
- "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
- "...) 的部分匹配值表(前缀、后缀共同元素的长度)
* @param dest 子串
* @return
*/
public static int[] kmpNext(