KMP 演算法
看了好多沒搞懂，然后看了海大的知乎一下子清晰了好多附海大鏈接
首先先理解一下PMT表：
現在有一個字串"ababababca"和一個用來匹配的子串“abababca”
對子串進行分割：
分為"a","ab","aba","abab","ababa","ababab" ,"abababc","abababca"
分別對這些分割的字串找到他們的前綴和后綴例如“aba” 的前綴有"a","a,b"后綴有'a','ba','ba'
前綴和后綴抑制的情況只有‘a'所以可以跳躍的最大距離就為1.我們根據這個子串來畫出PMT表
| char | a | b | a | b | a | b | c | a |
|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| value | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
下面我們先用代碼來實作一下具體在代碼求出PMT表的value值，
#include <stdio.h>
#define MAXN 100
#include <string.h>
int main() {
char str1[]= "abababca";
int next[MAXN];
int i = 0, j = -1 ; //使用-1為了好判斷第一個
while (i < strlen(str1)) {
if ( j== -1 ||str1[i] == str1[j]) {
next[i] = j;
++i;
++j;
printf("%d\n", i);
}
else {
j = next[j];
}
}
for (int i = 0; i < 8; ++i) {
++next[i];
}
for (int i = 0; i < 8; ++i) {
printf("%d ", next[i]);
}
return 0;
}
求出了PMT表后，我們就可以根據PMT表來優化字串匹配
主串：ababababca
字串：abababca
在c的位置出現了匹配失敗也就是意味著在前六個字符匹配都是成功的，此時來看一下PMT表也就是第5個數那邊（從0開始索引）value值為4，這意味著在C前4個字符與字串的前4個字符完全一致，此時我們進行匹配完全可以從子串的第五個字符開始，
來完整實作一下kmp匹配
int kmp(char* s1, char* s2) {
int i = 0;
int j = 0;
while (i < strlen(s1) || j < strlen(s2)) {
if (j == -1 || s1[i] == s2[j]) {
i++;
j++;
}
else {
j = next[j - 1];
}
}
if (j == strlen(s2)) {
return i - j;
}
return -1;
}
完整代碼：
#include <stdio.h>
#define MAXN 100
#include <string.h>
int next[MAXN];
int kmp(char* s1, char* s2) {
int i = 0;
int j = 0;
while (i < strlen(s1) || j < strlen(s2)) {
if (j == -1 || s1[i] == s2[j]) {
i++;
j++;
}
else {
j = next[j - 1];
}
}
if (j == strlen(s2)) {
return i - j;
}
return -1;
}
int main() {
char str1[]= "abababca";
char str2[] = "ababababca";
int i = 0, j = -1 ; //使用-1為了好判斷第一個
while (i < strlen(str1)) {
if ( j== -1 ||str1[i] == str1[j]) {
next[i] = j;
++i;
++j;
printf("%d\n", i);
}
else {
j = next[j];
}
}
for (int i = 0; i < 8; ++i) {
++next[i];
}
//for (int i = 0; i < 8; ++i) {
// printf("%d ", next[i]);
//}
int result = kmp(str2, str1);
if (result == -1) {
printf("不存在");
}
else {
printf("在第%d位置存在", result);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71911.html
標籤：其他
上一篇：找大佬
下一篇：關于疫情期間更換作業的問題