KMP 算法

本文主要是介绍KMP 算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

28. 实现 strStr()

如果字符串str中含有子串match，则返回match在str中的开始位置，不含有则返回-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 算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！