KMP 算法

来自:程序员代码面试指南:IT名企算法与数据结构题目最优解(第2版)左程云 P542

28. 实现 strStr()

如果字符串str中含有子串match,则返回matchstr中的开始位置,不含有则返回-1

KMP算法是如何快速解决字符串匹配问题的?

  1. 生成match字符串nextArr数组

nextArr[i]的含义

match[i]之前的字符串match[0..i-1]

match[i-1]结尾的后缀子串(不能包含match[0])与必须

match[0]开头的前缀子串(不能包含match[i-1])

最大匹配长度是多少,这个长度就是 nextArr[i]的值

上一篇:串定义、KMP算法


下一篇:MySQL5.5安装教程+SQLyog安装和使用