KMP演算法的三種匹配方法
文章目錄
- KMP演算法的三種匹配方法
- KMP演算法方法一：前綴表匹配查找
- 方法二：next[]陣列法
- 方法三：改進的next[]陣列，即nextval[]陣列法
宣告：
這三種匹配方式分別為：真前綴表、next[]陣列、nextval[]陣列匹配，其中真前綴表與next[]陣列平級，復雜度相同，而nextval[]為next[]的升級版，時間復雜度相比前兩者有顯著降低，
…
對于真前綴表，僅給出一種格式，即無論待匹配長串、還是待匹配短串，其陣列下標均是從0開始
對于next[]陣列和nextval[]陣列給出兩種格式，一種待匹配長串、還是待匹配短串，其陣列下標均是從0開始，另一種待匹配長串、還是待匹配短串，其陣列下標均是從1開始，
…
其實我個人認為字符陣列下標從0開始看起來更舒服，也更符合邏輯，但是有的人認為下標從1開始方便，可以巧妙避免很多問題的出現…所以我勉為其難地把字符陣列下標為1的格式列了出來，這波也算是致敬著有《大話資料結構》的程杰老師，
KMP演算法方法一：前綴表匹配查找
小目錄：
1. 求出前綴表繼而得到真前綴表
2. 根據前綴表進行匹配查找
1. 求出前綴表繼而得到真前綴表
*以下所講的子串均不包含其自身*
//簡介前綴表：前綴表即待匹配短串的子串的前綴，這句話中說，舉例如下
待匹配短串：ababax
其全部子串為：a、ab、aba、abab、ababa，這5子串對一一應一個前綴值
前綴值就是該子串的最大前后公共子串的長度，舉例介紹一下前綴值：
以上面 5個子串中其一abab為例：
因為子串不包括自身，所以前、后子串最長為3，前子串應該是aba(1-3)，后子串應該是bab(2-4)
因為前子串不等于后子串，所以不能稱之為“公共子串”，所以abab的前綴值不等于3
我們減少該前后子串長度，變為2，這時前子串是ab(1-2)，后子串是ab(3-4)，前子串等于后子串
所以對于abab來說公共子串是ab，長度為2，故abab的前綴值為2，由此可得對應前綴表：
(待匹配短串的)子串 前綴值 對應公共子串
a 0 無
ab 0 無
aba 1 a
abab 2 ab
ababa 3 aba
ababax 0 無
注：該項為了觀感，(串自身)其實不應該出現
得到前綴表(prefixtable)陣列： prefix[] = {0, 0, 1, 2, 3, 0}
接下來對前綴表進行加工，使其變為真前綴表，規則如下：
前綴表所有前綴值后移一位，最后一位資料(即上述ababax的前綴值)被覆寫
將前綴表首位賦值為-1，得到真前綴表，顯示如下：
prefix[] = {-1, 0, 0, 1, 2, 3}
2. 根據真前綴表進行匹配查找：見如下代碼
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;
const int N = 1010;
int main()
{
char text[N+1] = {0}, str[N] = {0};
cout << "請輸入主串：" << endl;
cin.getline(text, N - 1);
cout << "請輸入待匹配子串：" << endl;
cin >> str;
int m = strlen(text);
int n = strlen(str);
int *prefix = (int *)calloc(n, sizeof(int));
int i = 1, j = 0;
//
while (i < n)
{
if (str[i] == str[j])
{
j++;
prefix[i] = j;
i++;
}
else
{
if (j > 0) j = prefix[j-1];//斜下方回溯
else
{
prefix[i] = j;
i++;
}
}
}
for (i = n - 1; i > 0; i --)
prefix[i] = prefix[i-1];
prefix[0] = -1;
j = 0, i = 0;
while (i < m)
{
if (j == n - 1 && text[i] == str[j])
{
printf("在字串第 %d 個位置找到!\n", i - j + 1);
j = prefix[j];
}
if (text[i] == str[j])
i++, j++;
else
{
j = prefix[j];
if (j == -1) i ++, j ++;
}
}
return 0;
}
注：為了讓字串下標從1開始，為了方便，我們在輸入時多輸入一個空格，該空格起占位作用，但是在查找時，不算有效字符，以該空格后一個字符作為第一個字符位置
方法二：next[]陣列法
關于next陣列法，我簡單介紹一下，借用《大話資料結構》的公式進行說明
{ 0 , j = 1;
next[j] = { Max{k|1<k<j && 'p1...pk-1' = 'pj-k+1...pj-1'};不為空集
{ 1, 其他情況
p是下標從1開始的字串，舉ababx的例子
j = next[j] =
1 0
2 1
3 1
4 2
5 3
6 4
解釋一下：
當 j = 1 時， 直接按照式子可得next[1] = 0
當 j = 2 時， 分段一條件不滿足j = 1, 分段二條件不滿足，因為k的集合為空集
只有分段三滿足，故 next[2] = 1
當 j = 3 時，k 只能取 2，但是不滿足p1 = p2(即a = b)這個條件，所以這個k = 2不可取，k集合為空
只有分段三滿足，故next[3] = 1
當 j = 4時， k 可以取 2， 3
k = 2時， p1 = p3（即a = a)滿足條件，k 可以取到 2
k = 3時， p1p2 = p2p3(即ab = ba)不滿足條件， k 取不到 3
所以， k = {2}， next[4] = max{ k } = 2;
...
后面依次類推，就可得next[]陣列的所有值
- 兩字串下標從1開始的，next[]陣列法
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;
const int N = 1010;
int main()
{
char text[N+1] = {0}, str[N+1] = {0};
cout << "請輸入主串：" << endl;
cin.getline(text, N - 1);
cout << "請輸入待匹配子串：" << endl;
cin.getline(str, N - 1);
int i = 1, j = 0;
int m = strlen(text);
int n = strlen(str);
int* next = (int*)calloc(n, sizeof(int));
next[1] = 0;
while (i < n - 1)
{
if (j == 0 || str[i] == str[j])
{
++ i, ++ j;
next[i] = j;
}
else
j = next[j];//若字符不相同，則j值回溯(正下)
}
j = 1, i = 0;
while (i < m)
{
if (j == n)
{
printf("在字串第 %d 個位置找到!\n", i - j + 1);
j = 0;
}
if (j == 0 || text[i] == str[j]) ++i, ++ j;
else j = next[j-1];
}
return 0;
}
- 兩字串下標從0開始的，next[]陣列法
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;
const int N = 1010;
int main()
{
char text[N+1] = {0}, str[N+1] = {0};
cout << "請輸入主串：" << endl;
cin.getline(text, N - 1);
cout << "請輸入待匹配子串：" << endl;
cin >> str;
int i = 0, j = -1;
int m = strlen(text);
int n = strlen(str);
int* next = (int*)calloc(n, sizeof(int));
next[0] = -1;//為了讓匹配字串下標從0開始我容易嗎？
while (i < n - 1)
{
if (j == -1 || str[i] == str[j])
{
++ i, ++ j;
next[i] = j;
}
else
j = next[j];//若字符不相同，則j值回溯(正下)
}
for (i = 0; i < n; i ++)
next[i] += 1;//加工next[]以得到真正的next[]陣列
j = 0, i = 0;
while (i < m)
{
if (j == n - 1 && text[i] == str[j])
{
printf("在字串第 %d 個位置找到!\n", i - j + 1);
++i, j = 0;
}
if (text[i] == str[j]) ++ i, ++ j;
else
{
if (j == 0) ++ i;
else j = next[j-1];
}
}
return 0;
}
小結：下標從字串1開始確實方便很多的操作，如上所示，無論是在求next[]陣列，還是利用next[]陣列進行匹配查找的程序中，下標從0開始會遇到一些小問題，你可以看一下，下標從0開始算next[]陣列，其實是利用另一種思路求得“偽next[]”，再加工(next[i] = next[i] + 1)這一步得到的，在匹配程序中就更顯麻煩了，
方法三：改進的next[]陣列，即nextval[]陣列法
關于nextval[]陣列的求法，這里簡單介紹一下，這里的next[]陣列與上面的next[]陣列均出自程杰的《大話資料結構》
next[]轉 -- nextval[]規則：字串下標從1開始
{ 0; j = 1
nextval[j]= { next[j]; str[next[j]] = str[j] && j > 1
{ nextval[next[j]]; 其他情況
舉例說明如下：
j = 1 2 3 4 5 6 7 8 9
str： a b a b a a a b a
next[j]: 0 1 1 2 3 4 2 2 3
nextval[j]: 0 1 0 1 0 4 2 1 0
/* str為待匹配短串 */
當 j = 1 時， nextval[1] = 0;
當 j = 2 時， 因為第二位字符"b"的next值為1，而第一位就是“a”，它們不相等，
故nextval[2] = next[2] = 1, nextval[2]繼承next[2]原值
當 j = 3時， 因為第三位字符“a”的next值為1，而第一位就是"a"，它們相等，
故nextval[3] = nextval[1] = 0;
...
以此類推，可得nextval[]陣列的所有值
- 兩字串下標從1開始的，nextval[]陣列法
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;
const int N = 1010;
int main()
{
char text[N+1] = {0}, str[N+1] = {0};
cout << "請輸入主串：" << endl;
cin.getline(text, N - 1);
cout << "請輸入待匹配子串：" << endl;
cin.getline(str, N - 1);
int n = strlen(str);
int m = strlen(text);
int *next = (int *)calloc(n, sizeof(int));
int *nextval = (int *)calloc(n, sizeof(int));
int i = 1, j = 0;
nextval[0] = -1;
while (i < n)
{
if (j == 0 || str[i] == str[j])
{
++i, ++j;
next[i] = j;
}
else j = next[j];//若字符不相同，則j值回溯
}
i = 1, j = 0;
while (i < n)
{
if (j == 0 || str[i] == str[j])
{
++ i, ++ j;
if (str[i] != str[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else j = nextval[j];
}
j = 1, i = 1;
while (i < m)
{
if (j == n - 1 && text[i] == str[j])
{
printf("在字串第 %d 個位置找到!\n", i - j + 1);
j = 0;
}
if (j == 0 || text[i] == str[j]) ++ i, ++ j;
else j = nextval[j];
}
return 0;
}
2.兩字串下標從0開始的，nextval[]陣列法
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;
const int N = 1010;
int main()
{
int i = 1, j = 0, t = 0;
char text[N+1] = {0}, str[N+1] = {0};
cout << "請輸入主串：" << endl;
cin.getline(text, N - 1);
cout << "請輸入待匹配子串：" << endl;
cin >> str;
int n = strlen(str);
int m = strlen(text);
int *maxl = (int *)calloc(n, sizeof(int));
int *next = (int *)calloc(n, sizeof(int));
int *nextval = (int *)calloc(n, sizeof(int));
while (i < n)
{
if (str[i] == str[j])
{
j++;
maxl[i] = j;
i++;
}
else
{
if (j > 0) j = maxl[j - 1];
else
{
maxl[i] = j;
i++;
}
}
}
for (i = 1; i < n; i ++)//另一種方法計算next[]陣列
next[i] = maxl[i - 1] + 1;
nextval[0] = 0;
for (i = 1; i < n; i ++)
{
if (maxl[i] == next[i])//另一種方法計算nextval[]陣列
{
t = maxl[i];
nextval[i] = nextval[t - 1];
}
else
nextval[i] = next[i];
}
j = 0, i = 0;
while (i < m)
{
if (j == n - 1 && text[i] == str[j])
{
printf("在字串第 %d 個位置找到!\n", i - j + 1);
++ i;
j = 0;
}
if (text[i] == str[j]) ++ i, ++ j;
else
{
if (j == 0) ++ i;
else j = next[j - 1];
}
}
return 0;
}
總結： 真前綴表的方法可以直接套用，沒有什么好說的，重點在于next[]陣列、nextval[]陣列的方法，盡管求next[]陣列、nextval[]陣列的方法是多樣的，但其模式可歸納為兩部分：求next/nextval陣列、依照求得陣列回溯規則匹配字串
因為求next[]/nextval[]陣列方法很多，這里不在贅述
next[]陣列/nextval[]陣列 + 匹配模板
- 字串下標從0開始
//求出next[]陣列后，可套匹配模板，當然要根據
//你的實際情況進行改動這里僅作為一個參照
j = 0, i = 0;
while (i < m)//m為主字串長度， n為短串長度
{
if (j == n - 1 && text[i] == str[j])
{
printf("在字串第 %d 個位置找到!\n", i - j + 1);
++i, j = 0;
}
if (text[i] == str[j]) ++ i, ++ j;//text為主字串，str為短串
else
{
if (j == 0) ++ i;
else j = next[j-1];
}
}
- 字串下標從1開始
//這里注釋與上面一樣
j = 1, i = 1;
while (i < m)
{
if (j == n - 1 && text[i] == str[j])
{
printf("在字串第 %d 個位置找到!\n", i - j + 1);
j = 0;
}
if (j == 0 || text[i] == str[j]) ++ i, ++ j;
else j = next[j];
}
由此可見，同模式(即字串起點相同)只要next[]，可以運行，那么只需在匹配模板中將next[]改為nextval[]即可
所以，next[]陣列方法 —> nextval[]陣列法，僅僅需要在原來next[]陣列法的基礎上，加一步next[]轉化nextval[]，并將查找匹配模塊中的next[]改為nextval[]即可
最后，如果您對于next[]、nextval[]陣列的多種求法感興趣，不妨移步至我之前的一篇博客，里面具體介紹了該陣列的計算方法，點擊可至
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282266.html
標籤：其他
上一篇：Linux多執行緒(行程與執行緒，執行緒的生命周期認識執行緒，執行緒互斥)
下一篇：計算機簡略學習基礎筆記