KMP算法 Java实现

Problem: 28. 找出字符串中第一个匹配项的下标

目录

• 解题方法
  
• 思路
  
  
  
  • 构建next数组
    
  • 回溯查找
    
  
  
• 复杂度
  
• Code
  

解题方法

• 构建next串
  
• 回溯查找next串,最后下标
  

思路

• 通过最大前缀后缀能找到下一次未查找到后要回溯的位置
  

构建next数组

无论如何第一个数的下一次回溯位置肯定是0,因此next[0]=0
这里的 j表示前缀起始位置 i表示后缀起始位置
假如找到字符不相同到的话,就让他一直回溯找,并且回溯赋值j = next[j-1]
能找到相同字符的话就直接i++,j++,并且把next = j
这里先写while判断不相同 后写相同,是因为不相同的终点
一定是有相同的后缀或者直接竣事查找(到了字符串末尾)
回溯查找

其实和上面的思路差不多,不能查找相同字符就一直回溯,能的话就共同前进,直到j到了模式串长度
这时因为i也在前进,以是i的下标是  应该返回的下标+(匹配串的长-1)
复杂度

时间复杂度:

添加时间复杂度, 示例： $O(m+n)$

空间复杂度:

添加空间复杂度, 示例： $O(m)$

Code

1. class Solution {
3.     public int strStr(String haystack, String needle) {
4.         return new KMP(needle).search(haystack);
5.     }
7.     public class KMP {
8.         private String pattern;   // 模式串
9.         private int[] next;
10.         public KMP(String pattern){
11.             this.pattern = pattern;
12.             int m = pattern.length();
13.             // 创建next 数组
14.             next = new int[m];
15.             next[0] = 0;
16.             for(int i = 1,j=0; i < m; i++){
17.                 while(j>0&&pattern.charAt(i)!=pattern.charAt(j)){
18.                     j = next[j-1];
19.                 }
20.                 if(pattern.charAt(i) == pattern.charAt(j)){
21.                     j++;
22.                 }
23.                 next[i] = j;
24.             }
25.         }
27.         public int search(String text){
28.             int j = 0;
29.             for(int i=0;i<text.length();i++){
30.                 while(j>0&&text.charAt(i) != pattern.charAt(j)){
31.                     j = next[j-1];
32.                 }
33.                 if(text.charAt(i) == pattern.charAt(j)){
34.                     j++;
35.                 }
36.                 if(j == pattern.length()){
37.                     return i-pattern.length()+1;
38.                 }
39.             }
40.             return -1;
41.         }
42.     }
44. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。