您好,登錄后才能下訂單哦!
Knuth-Morris-Pratt(KMP)算法是一種高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris于1977年提出。KMP算法的核心思想是利用已經(jīng)匹配的部分信息,避免在文本串中的回溯,從而提高字符串匹配的效率。
KMP算法的主要步驟如下:
構(gòu)建最長(zhǎng)公共前后綴數(shù)組(也稱為部分匹配表):這個(gè)數(shù)組用于存儲(chǔ)模式串(pattern)中每個(gè)位置的最長(zhǎng)公共前后綴長(zhǎng)度。例如,對(duì)于模式串"ABABAC",最長(zhǎng)公共前后綴數(shù)組為{0, 0, 1, 2, 0, 1}。
在文本串(text)中進(jìn)行匹配:從文本串的第一個(gè)字符開(kāi)始,與模式串的第一個(gè)字符進(jìn)行比較。如果相等,則繼續(xù)比較下一個(gè)字符;如果不相等,則根據(jù)當(dāng)前模式串中已匹配的部分,查找最長(zhǎng)公共前后綴數(shù)組,確定下一個(gè)需要比較的模式串字符的位置。重復(fù)這個(gè)過(guò)程,直到找到匹配的子串或者比較完整個(gè)文本串。
KMP算法的時(shí)間復(fù)雜度為O(n+m),其中n為文本串的長(zhǎng)度,m為模式串的長(zhǎng)度。這使得KMP算法在處理大量數(shù)據(jù)時(shí)具有較高的效率。
以下是一個(gè)簡(jiǎn)單的KMP算法實(shí)現(xiàn)(C語(yǔ)言):
#include<stdio.h>
#include<string.h>
void compute_lps(char* pattern, int M, int* lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
void kmp_search(char* text, char* pattern) {
int N = strlen(text);
int M = strlen(pattern);
int lps[M];
compute_lps(pattern, M, lps);
int i = 0; // Index for text
int j = 0; // Index for pattern
while (i < N) {
if (pattern[j] == text[i]) {
i++;
j++;
}
if (j == M) {
printf("Pattern found at index %d\n", i - j);
j = lps[j - 1];
} else if (i < N && pattern[j] != text[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
}
int main() {
char text[] = "ABABABCABABABC";
char pattern[] = "ABABAC";
kmp_search(text, pattern);
return 0;
}
這段代碼首先計(jì)算了模式串"ABABAC"的最長(zhǎng)公共前后綴數(shù)組,然后在文本串"ABABABCABABABC"中查找該模式串。運(yùn)行結(jié)果將輸出"Pattern found at index 6",表示在文本串中找到了模式串的匹配。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。