完整的kmp过程见下方 4. 可能有帮助的前置习题
1. 题目
2. 读题(需要重点注意的东西)
思路(kmp算法):
思路分析与[AcWing]831. KMP字符串(C++实现)KMP模板题完全相同,在此不再赘述。
3. 解法
---------------------------------------------------解法---------------------------------------------------:
class Solution {
public int strStr(String haystack , String needle) {
// 当 needle 是空字符串时,直接返回0
if(needle.length() < 1) return 0;
int n = haystack.length();
int m = needle.length();
// 将haystack和needle转为数组,使s串和p串都从数组下标1开始计数
char[] s = (" " + haystack).toCharArray();
char[] p = (" " + needle).toCharArray();
// 定义ne数组
int[] ne = new int[m + 10];
// 构建ne数组
// 注意:此处构建ne数组,i是从2开始的
for(int i = 2,j = 0;i <= m;i ++)
{
// !!核心!!:跳转
while(j != 0 && p[i] != p[j + 1]) j = ne[j];
// 如果字符串匹配,则匹配下一个字符
if(p[i] == p[j + 1]) j ++;
ne[i] = j;
}
// 根据ne数组进行匹配
// 注意:进行匹配时,i是从1开始的
for(int i = 1,j = 0;i <= n;i ++)
{
while(j != 0 && s[i] != p[j + 1]) j = ne[j];
// 如果匹配,则继续匹配下一个字符
if(s[i] == p[j + 1]) j ++;
// 如果完全匹配
if(j == m)
{
j = ne[j];
// 返回匹配开始的下标
return i - m;
}
}
// 不存在,返回-1
return -1;
}
}
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
- kmp算法
6. 总结
kmp算法的模板题,背下来!