BoyerMoore(text, pattern):
n = len(text)
m = len(pattern)
# Előfeldolgozás
bad_char = create_bad_char_table(pattern)
good_suffix = create_good_suffix_table(pattern)
i = 0
while i <= n - m:
j = m - 1
while j >= 0 and pattern == text:
j -= 1
if j < 0:
print(f"Minta megtalálva itt: {i}")
i += good_suffix
else:
shift = max(1, j - bad_char])
i += shift
def create_bad_char_table(pattern):
bad_char = * 256 # ASCII karakterek
for i in range(len(pattern)):
bad_char)] = i
return bad_char
def create_good_suffix_table(pattern):
m = len(pattern)
good_suffix = * m
border = * (m + 1)
j = m
for i in range(m - 1, -1, -1):
if pattern == pattern:
border = i + 1
j -= 1
j = 0
for i in range(m):
if border == 0:
good_suffix = m - j
else:
good_suffix = m - border
j += 1
return good_suffix
def boyer_moore(text, pattern):
n = len(text)
m = len(pattern)
if m == 0:
return
# Előfeldolgozás
bad_char = create_bad_char_table(pattern)
good_suffix = create_good_suffix_table(pattern)
i = 0
results =
while i <= n - m:
j = m - 1
while j >= 0 and pattern == text:
j -= 1
if j < 0:
results.append(i)
i += good_suffix
else:
i += max(1, j - bad_char)])
return results
# Példa
text = "ABAAABCDABC"
pattern = "ABC"
result = boyer_moore(text, pattern)
print("A minta megtalálható pozíciói:", result)
Kimenet:
A minta megtalálható pozíciói:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<int> create_bad_char_table(const string& pattern) {
vector<int> bad_char(256, -1); // ASCII karakterek
for (int i = 0; i < pattern.size(); ++i) {
bad_char] = i;
}
return bad_char;
}
vector<int> boyer_moore(const string& text, const string& pattern) {
int n = text.size();
int m = pattern.size();
vector<int> result;
if (m == 0) return result;
vector<int> bad_char = create_bad_char_table(pattern);
int shift = 0;
while (shift <= n - m) {
int j = m - 1;
while (j >= 0 && pattern == text) {
--j;
}
if (j < 0) {
result.push_back(shift);
shift += (shift + m < n) ? m - bad_char] : 1;
} else {
shift += max(1, j - bad_char]);
}
}
return result;
}
int main() {
string text = "ABAAABCDABC";
string pattern = "ABC";
vector<int> positions = boyer_moore(text, pattern);
cout << "A minta megtalálható pozíciói: ";
for (int pos : positions) {
cout << pos << " ";
}
cout << endl;
return 0;
}
Kimenet:
A minta megtalálható pozíciói: 4 8
A Boyer-Moore-algoritmus az egyik leggyorsabb szövegkeresési algoritmus, amelyet különösen nagy szövegek és minták keresésére használnak. A Bad Character és a Good Suffix heurisztikák kombinációja révén az algoritmus hatékonyan csökkenti az összehasonlítások számát, így a gyakorlatban nagyon gyors. Ezért az algoritmus népszerű választás, ha nagy adathalmazokban kell keresni mintákat.