資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學KMP 演算法模式搜尋的 C 程式
在這個問題中，我們得到了兩個字串，一個文字和一個模式。我們的任務是建立一個用於模式搜尋的 KMP 演算法程式，它將找到文字字串中模式的所有出現。
在這裡，我們必須找到文字中所有模式的出現。
讓我們舉個例子來理解這個問題，
輸入
text = “xyztrwqxyzfg” pattern = “xyz”
輸出
Found at index 0 Found at index 7
在這裡，我們將討論使用 KMP（Knuth Morris Pratt）模式搜尋演算法解決問題的方案，它將使用模式的預處理字串，該字串將用於在文字中進行匹配。並在匹配字元後面跟著不匹配模式的字串字元的情況下，幫助處理或查詢模式匹配。
我們將預處理模式並建立一個數組，其中包含來自模式的適當字首和字尾，這將有助於查詢不匹配模式。
KMP 演算法模式搜尋程式
// KMP 演算法模式搜尋的 C 程式
示例
#include<iostream>
#include<string.h>
using namespace std;
void prefixSuffixArray(char* pat, int M, int* pps) {
int length = 0;
pps[0] = 0;
int i = 1;
while (i < M) {
if (pat[i] == pat[length]) {
length++;
pps[i] = length;
i++;
} else {
if (length != 0)
length = pps[length - 1];
else {
pps[i] = 0;
i++;
}
}
}
}
void KMPAlgorithm(char* text, char* pattern) {
int M = strlen(pattern);
int N = strlen(text);
int pps[M];
prefixSuffixArray(pattern, M, pps);
int i = 0;
int j = 0;
while (i < N) {
if (pattern[j] == text[i]) {
j++;
i++;
}
if (j == M) {
printf("Found pattern at index %d
", i - j);
j = pps[j - 1];
}
else if (i < N && pattern[j] != text[i]) {
if (j != 0)
j = pps[j - 1];
else
i = i + 1;
}
}
}
int main() {
char text[] = "xyztrwqxyzfg";
char pattern[] = "xyz";
printf("The pattern is found in the text at the following index :
");
KMPAlgorithm(text, pattern);
return 0;
}輸出
模式在以下索引處的文字中找到 -
Found pattern at index 0 Found pattern at index 7
更新於: 2020-07-17
8K+ 次檢視
廣告