首页 > 基础资料 博客日记
KMP算法 Java实现
2024-04-17 13:30:02基础资料围观262次
Java资料网推荐KMP算法 Java实现这篇文章给大家,欢迎收藏Java资料网享受知识的乐趣
Problem: 28. 找出字符串中第一个匹配项的下标
解题方法
- 构建next串
- 回溯查找next串,最后下标
思路
- 通过最大前缀后缀能找到下一次未查找到后要回溯的位置
构建next数组
无论如何第一个数的下一次回溯位置肯定是0,因此next[0]=0
这里的 j
表示前缀起始位置 i
表示后缀起始位置
如果找到字符不相同到的话,就让他一直回溯找,并且回溯赋值j = next[j-1]
能找到相同字符的话就直接i++,j++
,并且把next[i] = j
这里先写while
判断不相同 后写相同,是因为不相同的终点
一定是有相同的后缀或者直接结束查找(到了字符串末尾)
回溯查找
其实和上面的思路差不多,不能查找相同字符就一直回溯,能的话就共同前进,直到j到了模式串长度
这时因为i也在前进,所以i的下标是 应该返回的下标+(匹配串的长-1)
复杂度
时间复杂度:
添加时间复杂度, 示例: $O(m+n)$
空间复杂度:
添加空间复杂度, 示例: $O(m)$
Code
class Solution {
public int strStr(String haystack, String needle) {
return new KMP(needle).search(haystack);
}
public class KMP {
private String pattern; // 模式串
private int[] next;
public KMP(String pattern){
this.pattern = pattern;
int m = pattern.length();
// 创建next 数组
next = new int[m];
next[0] = 0;
for(int i = 1,j=0; i < m; i++){
while(j>0&&pattern.charAt(i)!=pattern.charAt(j)){
j = next[j-1];
}
if(pattern.charAt(i) == pattern.charAt(j)){
j++;
}
next[i] = j;
}
}
public int search(String text){
int j = 0;
for(int i=0;i<text.length();i++){
while(j>0&&text.charAt(i) != pattern.charAt(j)){
j = next[j-1];
}
if(text.charAt(i) == pattern.charAt(j)){
j++;
}
if(j == pattern.length()){
return i-pattern.length()+1;
}
}
return -1;
}
}
}
文章来源:https://www.cnblogs.com/xiaofengs/p/18140402
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签: