Boyer-Moore-Horspool-algoritmus
A Boyer-Moore-Horspool-algoritmus egy hatékony szövegkereső algoritmus, amelyet arra terveztek, hogy egy adott mintát (pattern) keressen egy szövegben (text). Ez az algoritmus egy egyszerűsített változata a Boyer-Moore algoritmusnak, de a legtöbb esetben gyorsabb, mert kevesebb szabályt használ.
def boyer_moore_horspool(text, pattern):
"""
Boyer-Moore-Horspool algoritmus szövegkereséshez.
:param text: Szöveg, amelyben keresünk.
:param pattern: A keresett minta.
:return: Az egyezés kezdőindexe(i), vagy -1, ha nincs egyezés.
"""
m = len(pattern)
n = len(text)
if m > n:
return -1
# Eltolási táblázat előállítása
shift = {char: m for char in set(text)}
for i in range(m - 1):
shift] = m - i - 1
# Szöveg keresése
i = 0
while i <= n - m:
j = m - 1
while j >= 0 and pattern == text:
j -= 1
if j < 0: # Egyezést találtunk
return i
i += shift.get(text, m) # Előrelépés az eltolási táblázat alapján
return -1
# Példa használat
text = "hello there, this is an example"
pattern = "example"
index = boyer_moore_horspool(text, pattern)
if index != -1:
print(f"Minta megtalálva a(z) {index}. indexen.")
else:
print("Minta nem található.")
Kimenet:
Minta megtalálva a(z) 21. indexen.
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int boyerMooreHorspool(const string& text, const string& pattern) {
int m = pattern.size();
int n = text.size();
if (m > n) {
return -1;
}
// Eltolási táblázat előállítása
unordered_map<char, int> shift;
for (char c : text) {
shift = m;
}
for (int i = 0; i < m - 1; ++i) {
shift] = m - i - 1;
}
// Szöveg keresése
int i = 0;
while (i <= n - m) {
int j = m - 1;
while (j >= 0 && pattern == text) {
--j;
}
if (j < 0) { // Egyezést találtunk
return i;
}
i += shift.count(text) ? shift] : m;
}
return -1;
}
int main() {
string text = "hello there, this is an example";
string pattern = "example";
int index = boyerMooreHorspool(text, pattern);
if (index != -1) {
cout << "Minta megtalálva a(z) " << index << ". indexen." << endl;
} else {
cout << "Minta nem található." << endl;
}
return 0;
}
Kimenet:
Minta megtalálva a(z) 21. indexen.
Ez a megközelítés könnyen implementálható és hatékony sok gyakorlati esetben.