KMP算法和next數組詳解

zhanghangqian 2022-01-08 03:25:04 阅读数:459

kmp 算法

KMP算法主要是用來求解子串在主串中第一次出現的比特置,並返回這個子串的比特置的一種提高效率的方法。在講解KMP算法之前,我們先來看看求子串在主串中比特置的一般解法,即暴力解法。

 

1.暴力解法

 public static int BF(String str,String sub){
if(str == null || sub == null){
return -1;
}
int lenStr = str.length();
int lenSub = sub.length();
if(lenStr == 0 || lenSub == 0){
return -1;
}
int i = 0;
int j = 0;
while (i < lenStr && j < lenSub ){
if(str.charAt(i) == sub.charAt(j)){
i++;
j++;
}else {
i = i - j + 1;
j = 0;
}
}
if(j >= lenSub){
return i-j;
}
return -1;
}
public static void main(String[] args) {
System.out.println(BF("ababcabcdabcde","abcd"));
System.out.println(BF("ababcabcdabcde","abcf"));
System.out.println(BF("ababcabcdabcde","ab"));
}

 2.KMP算法

        KMP算法和暴力解法的區別就是,在暴力解法主串中如果i和子串j中不匹配,則i返回到開始匹配的地方並+1,但KMP中不用返回,繼續保持在原比特。在子串中的j會返回到一個“特殊”比特置,而這個特殊比特置就是我們接下來要講的。

首先我們看看什麼叫next數組:

2.1next數組的含義:

 2.2next數組練習

(1).  k值的求法:找到匹配成功部分的兩個相等的真子串(不包含本身),一個以下標0開始,一個以下標j-1結尾。

(2).  不管什麼時候next[0]都=-1,next[1]=0.

2.2.1例題1

 例題2:

 2.3求解數組next[i+1]的值

         我們通過上面自己的計算可以求得next[i+1]數組得值,但是我們用程序就需要一個函數來解决,下面我們來求其函數:

 推導過程:從上圖之第一次k退回到p[3]的比特置,假設p[i] == p[k]

 那如果p[i] != p[k]時:next[i+1]=什麼呢?

3.java來實現代碼

第一步:進入遍曆主串和子串的條件

//首先我們先來列出條件
public static int KMP(String str,String sub,int pos){
if(str == null || sub ==null){
return -1;
}
int lenStr = str.length();
int lenSub = sub.length();
if(lenStr == 0 || lenSub == 0){
return -1;
}
if(pos < 0 || pos >= lenStr){
return -1;
}

第二步:進行主串和子串的遍曆

 int i = pos;//遍曆主串
int j = 0;//遍曆子串
while (i < lenStr && j < lenSub){
//j==-1錶示一開始就匹配失敗
if(j==-1 || str.charAt(i) == sub.charAt(j)){
i++;
j++;
}else {
j = next[j];
}
}
if(j >= lenSub){
return i-j;
}
return -1;
}

第三步:寫出next數組,來保存子串j回退的比特置

int [] next = new int[lenSub];
getNext(sub,next);//求得j回退得比特置
public static void getNext(String sub,int[] next){
next[0] = -1;//開始的next[0]默認是-1
next[1] = 0;//默認next[1]是0
int i = 2;//默認i從第三個比特置開始
int k = 0;
for (; i < sub.length();i++) {
//p[i-1] == p[k];
//這裏是sub.charAt(i - 1)是因為之前i是從第三個比特置開始的,要用i的前一項
if (k==-1 || sub.charAt(i - 1) == sub.charAt(k)) {
next[i] = k+1;//之前計算得都是next[i+1]=k+1,這裏是因為i是第三個比特置開始
//得,因此是next[i]=k+1;
k++;
i++;
}else{
k = next[k];//如果第一次退回的k和之前的sub.charAt(i-1)不同,則繼續往下退
}
}
}

4.next的簡化數組nextval數組

 

版权声明:本文为[zhanghangqian]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080325037718.html