數據結構篇——KMP演算法
數據結構篇——KMP演算法
本次我們介紹數據結構中的KMP演算法，我們會從下面幾個角度來介紹：
- 問題介紹
- 暴力求解
- 知識補充
- Next示例
- Next程式碼
- 匹配示例
- 匹配程式碼
- 完整程式碼
問題介紹
首先我們先介紹適用於KMP演算法的問題：
- 給定一個字元串S，以及一個模式串P,所有字元串中只包含大小寫英文字母以及阿拉伯數字。
- 模式串P在字元串S中多次作為子串出現。
- 求出模式串P在字元串S中所有出現的位置的起始下標。
我們給出一個問題的簡單示例：
// 輸入 p長度 p s長度 s
3
aba
5
ababa
// 輸出結果
0 2
暴力求解
所有問題我們都是在暴力求解的基礎上進行更新迭代的，所以我們首先給出暴力求解：
// 下面為偽程式碼，只是起到思路作用
// 首先我們需要創造s[],p[]，並賦值
S[N],P[N]
// 然後我們開始匹配，我們會從S的第一個字元開始匹配，設置一個flag判斷該字元開始的字元串是否與P字元匹配
// 該演算法從每個i開始，全部進行匹配
for(int i = 1;i <= n;i++ ){
boolean flag = true;
for(int j = 1;j <= m;j++){
if(s[i+j-1] != p[j]){
flag = false;
break;
}
}
}
// 我們給出一套完整的暴力求解方法
/**
* 暴力破解法
* @param ts 主串
* @param ps 模式串
* @return 如果找到，返回在主串中第一個字元出現的下標，否則為-1
*/
public static int bf(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int i = 0; // 主串的位置
int j = 0; // 模式串的位置
while (i < t.length && j < p.length) {
if (t[i] == p[j]) {
// 當兩個字元相同，就比較下一個
i++;
j++;
} else {
i = i - j + 1; // 一旦不匹配，i後退（從之前i的下一位開始，也是遍歷所有i）
j = 0; // j歸0
}
}
// 當上面循環結束，必定是i到頭或者j到頭，如果是j到頭，則說明存在子串符合父串，我們就將頭位置i返回
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
// 但是我們會發現：我們可以不讓i回退而是讓j回退，使j回退到能夠與當前i相匹配的點位，然後繼續進行主串和模式串的匹配
首先我們會發現這個演算法的時間複雜度為O(n^2)
我們其中可以優化的點就是i的位置更新，我們可以根據p字元串的特性來判斷i在失敗後最近可以移動到哪個點位！
知識補充
我們為了學習KMP演算法，我們需要補充一些下面會用到的知識：
- s[ ]是模式串，即比較長的字元串。
- p[ ]是模板串，即比較短的字元串。（這樣可能不嚴謹。。。）
- 「非平凡前綴」：指除了最後一個字元以外，一個字元串的全部頭部組合。
- 「非平凡後綴」：指除了第一個字元以外，一個字元串的全部尾部組合。（後面會有例子，均簡稱為前/後綴）
- 「部分匹配值」：前綴和後綴的最長共有元素的長度。
- next[ ]是「部分匹配值表」，即next數組，它存儲的是每一個下標對應的「部分匹配值」，是KMP演算法的核心。（後面作詳細講解）。
我們所用到的思想是：
- 在每次失配時，不是把p串往後移一位，而是把p串往後移動至下一次可以和前面部分匹配的位置，這樣就可以跳過大多數的失配步驟
- 而每次p串移動的步數就是通過查找next[ ]數組確定的
Next示例
我們給出一個簡單的Next示例：
// 首先我們給出一個next手寫實例
/*
模板串為：ABABAA
next[0]代表t[0]-t[0]，即"A" , "A"的前綴和後綴都為空集，共有元素的長度為0.
next[1]代表t[0]-t[1]，即"AB"，前綴為「A」，後綴為「B」,共有元素的長度為0..
next[2]代表t[0]~t[2]，即"ABA"，前綴為「AB"，後綴為"BA"，最大前後綴即"A",長度為1.
next[3]代表t[0]~t[3]，即"ABAB"，前綴為"ABA"後綴為"BAB」,最大前後綴即"AB ",長度為2.
next[4]代表t[0]~t[4]，即"ABABA",前綴為"ABAB"，後綴為"BABA",最大前後綴即" ABA",長度為3.
next[5]代表t[0]-t[5]，即" ABABAA",前綴為「ABABA",T後綴為「BABAA";最大前後綴即"A",長度為1.
*/
// 我們next的作用是使next[j]=k使 P[0 ~ k-1] == P[j-k ~ j-1]、
// 當第n個數不匹配時，我們讓j回退到k，這時我們的主串和模式串的前綴還屬於匹配狀態，我們繼續進行匹配
例如 ababc
我們如果匹配到c不符合時，我們可以使j回退到k（這裡的k是2，即a）再繼續進行匹配
因為我們的c前面的ab和開頭的ab是匹配的，我們主串中的i前面肯定也是ab，我們的l前面也是ab，所以兩者匹配，我們可以繼續後面的匹配
相當於我們的x不變，我們將j放在2的位置，前面的ab已完成匹配，我們只需要匹配abc即可
// 公式書寫就是下述：
當T[i] != P[j]時
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然：T[i-k ~ i-1] == P[0 ~ k-1]
Next程式碼
我們給出求解Next的程式碼展示：
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
// 這裡的next[0]需要等於-1
// 因為j在最左邊時，不可能再移動j了，這時候要應該是i指針後移。所以在程式碼中才會有next[0] = -1;這個初始化。
next[0] = -1;
// 這裡設置j的初始值從第一個開始（我們需要得到全部next數組）
int j = 0;
// 這裡設置k，k就是應該返回的位置，也就是我們常說的前綴和後綴匹配區域的前綴的後一個位置
int k = -1;
// 進行循環，得到next數組
while (j < p.length - 1) {
// 首先是k==-1時，說明前面已無匹配狀態，我們重新開始
// 然後是p[j] == p[k]，說明循環時新添加的值，與我們應該返回比對的位置相同
// 同時由於我們之前的部分都是已經匹配成功的，所以加上這個數使我們的匹配長度又增加一位
if (k == -1 || p[j] == p[k]) {
// 當兩個字元相等時要跳過（因為p[k]與S[i]不符合的話，由於我們的p[j]=p[k]，所以肯定也不符合，我們直接跳下一步）
if (p[++j] == p[++k]) {
next[j] = next[k];
} else {
// 因為在P[j]之前已經有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）
// 這時候現有P[k] == P[j]，我們是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
// 即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1
// 前面我們已經進行了j++和k++，所以這裡直接賦值即可
next[j] = k;
}
} else {
// 如果當前狀態無法匹配，我們就跳回上一個前綴後綴相同部分再來判斷是否前後綴相同
k = next[k];
}
}
return next;
}
匹配示例
我們給出簡單的匹配示例：
// 匹配相對而言就比較簡單了
主串：abababc
模式串：abc
我們首先進行i++，j++範圍的匹配，當第三位，即a和c匹配不成功時，我們不移動i，而是移動j
我們將j=2,移動到j=0,即next[2]的位置，在之後一直匹配並再對j進行一次移動，到最後匹配成功為止
匹配程式碼
我們給出對應的匹配程式碼：
/*該程式碼實際上是由暴力求解程式碼改造過來的*/
public static int KMP(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int i = 0; // 主串的位置
int j = 0; // 模式串的位置
int[] next = getNext(ps);
// 開始判斷（設置邊界值）
while (i < t.length && j < p.length) {
// 當j為-1時，要移動的是i，當然j也要歸0
// 如果匹配成功，兩者都進行移動，開始下一位比對
if (j == -1 || t[i] == p[j]) {
i++;
j++;
} else {
// 如果比對失敗，我們將 j 返回next數組指定位置繼續匹配
// i不需要回溯了
// i = i - j + 1;
j = next[j]; // j回到指定位置
}
}
// 最後同樣進行判斷，是否符合條件
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
完整程式碼
最後為大家展示一下完整程式碼：
import java.util.Scanner;
class ppp {
/**
* 主程式碼
* @param args
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String ts = scanner.nextLine();
String ps = scanner.nextLine();
int kmp = KMP(ts, ps);
System.out.println(kmp);
}
/**
* kmp演算法
* @param ts
* @param ps
* @return
*/
public static int KMP(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int i = 0; // 主串的位置
int j = 0; // 模式串的位置
int[] next = getNext(ps);
// 開始判斷（設置邊界值）
while (i < t.length && j < p.length) {
// 當j為-1時，要移動的是i，當然j也要歸0
// 如果匹配成功，兩者都進行移動，開始下一位比對
if (j == -1 || t[i] == p[j]) {
i++;
j++;
} else {
// 如果比對失敗，我們將 j 返回next數組指定位置繼續匹配
// i不需要回溯了
// i = i - j + 1;
j = next[j]; // j回到指定位置
}
}
// 最後同樣進行判斷，是否符合條件
if (j == p.length) {
return i - j;
} else {
return -1;
}
}
/**
* next數組求解
* @param ps
* @return
*/
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
// 這裡的next[0]需要等於-1
// 因為j在最左邊時，不可能再移動j了，這時候要應該是i指針後移。所以在程式碼中才會有next[0] = -1;這個初始化。
next[0] = -1;
// 這裡設置j的初始值從第一個開始（我們需要得到全部next數組）
int j = 0;
// 這裡設置k，k就是應該返回的位置，也就是我們常說的前綴和後綴匹配區域的前綴的後一個位置
int k = -1;
// 進行循環，得到next數組
while (j < p.length - 1) {
// 首先是k==-1時，說明前面已無匹配狀態，我們重新開始
// 然後是p[j] == p[k]，說明循環時新添加的值，與我們應該返回比對的位置相同
// 同時由於我們之前的部分都是已經匹配成功的，所以加上這個數使我們的匹配長度又增加一位
if (k == -1 || p[j] == p[k]) {
// 當兩個字元相等時要跳過
//（因為p[k]與S[i]不符合的話，由於我們的p[j]=p[k]，所以肯定也不符合，我們直接跳下一步）
if (p[++j] == p[++k]) {
next[j] = next[k];
} else {
// 因為在P[j]之前已經有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）
// 這時候現有P[k] == P[j]，我們是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。
// 即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1
// 前面我們已經進行了j++和k++，所以這裡直接賦值即可
next[j] = k;
}
} else {
// 如果當前狀態無法匹配，我們就跳回上一個前綴後綴相同部分再來判斷是否前後綴相同
k = next[k];
}
}
return next;
}
}
結束語
好的，關於數據結構篇的KMP演算法就介紹到這裡，希望能為你帶來幫助~
