A Knuth-Morris-Pratt (KMP) algoritmus egy hatékony sztringkeresési algoritmus, amely egy szövegben találja meg egy adott minta előfordulását. Az algoritmus előfeldolgozza a mintát, hogy gyorsabban találhassa meg a lehetséges egyezéseket, elkerülve az ismételt összehasonlításokat.
ComputePrefixFunction(P):
m = P hossza
pi = * m // Prefix-függvény
j = 0 // Prefix hossza
ciklus i = 1-től m-1-ig:
amíg j > 0 és P != P:
j = pi
ha P == P:
j = j + 1
pi = j
térj vissza pi
KMP(T, P):
n = T hossza
m = P hossza
pi = ComputePrefixFunction(P)
j = 0 // Minta pozíciója
ciklus i = 0-tól n-1-ig:
amíg j > 0 és T != P:
j = pi
ha T == P:
j = j + 1
ha j == m:
return i - m + 1 // Talált egyezés kezdőpozíciója
j = pi
térj vissza -1 // Nincs egyezés
def compute_prefix_function(pattern):
m = len(pattern)
pi = * m
j = 0 # Prefix hossza
for i in range(1, m):
while j > 0 and pattern != pattern:
j = pi
if pattern == pattern:
j += 1
pi = j
return pi
def kmp_search(text, pattern):
n = len(text)
m = len(pattern)
pi = compute_prefix_function(pattern)
j = 0 # Minta pozíciója
for i in range(n):
while j > 0 and text != pattern:
j = pi
if text == pattern:
j += 1
if j == m:
return i - m + 1 # Egyezés kezdőpozíciója
j = pi
return -1 # Nincs egyezés
# Példa használat
text = "ababcabcabababd"
pattern = "ababd"
result = kmp_search(text, pattern)
print(f"A minta kezdőpozíciója: {result}" if result != -1 else "Nincs egyezés.")
Kimenet:
A minta kezdőpozíciója: 10
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> compute_prefix_function(const string& pattern) {
int m = pattern.size();
vector<int> pi(m, 0);
int j = 0;
for (int i = 1; i < m; ++i) {
while (j > 0 && pattern != pattern) {
j = pi;
}
if (pattern == pattern) {
j++;
}
pi = j;
}
return pi;
}
int kmp_search(const string& text, const string& pattern) {
int n = text.size();
int m = pattern.size();
vector<int> pi = compute_prefix_function(pattern);
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && text != pattern) {
j = pi;
}
if (text == pattern) {
j++;
}
if (j == m) {
return i - m + 1; // Egyezés kezdőpozíciója
}
}
return -1; // Nincs egyezés
}
int main() {
string text = "ababcabcabababd";
string pattern = "ababd";
int result = kmp_search(text, pattern);
if (result != -1) {
cout << "A minta kezdőpozíciója: " << result << endl;
} else {
cout << "Nincs egyezés." << endl;
}
return 0;
}
Kimenet:
A minta kezdőpozíciója: 10
A KMP algoritmus kiváló választás nagy szövegek gyors keresésére, például DNS-keresés, szövegbányászat vagy kódegyezés esetén.