来自:程序员代码面试指南:IT名企算法与数据结构题目最优解(第2版)左程云 P542
28. 实现 strStr()
如果字符串str
中含有子串match
,则返回match
在str
中的开始位置,不含有则返回-1
KMP算法是如何快速解决字符串匹配问题的?
- 生成
match字符串
的nextArr数组
nextArr[i]的含义
在match[i]
之前的字符串match[0..i-1]
中
以match[i-1]
结尾的后缀子串(不能包含match[0]
)与必须
以match[0]
开头的前缀子串(不能包含match[i-1
])
最大匹配长度是多少,这个长度就是 nextArr[i]
的值