Алгоритмы на строках
Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм)
Поиск подстроки в строке: даны образец для поиска $S$ и строка $T$, найти индекс, начиная с которого $S$ содержится в строке $T$. Если $S$ не содержится в $T$ - вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число).
При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.
Описание алгоритма и оценка времени работы
Рассмотрим сравнение строк на позиции $i$, где образец $S[0, m - 1]$ сопоставляется с частью текста $T[ i, i + m - 1 ]$. Предположим, что первое несовпадение произошло между $T[i + j]$ и $S[ j ]$, где $1 < j < m$. Тогда $T[ i, i + j - 1 ] = S[ 0, j - 1 ] = P$ и $a = T[ i + j ] \ne S[ j ] = b$.
При сдвиге вполне можно ожидать, что префикс (начальные символы) образца $S$ сойдется с каким-нибудь суффиксом (конечные символы) текста $P$. Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть префикс-функция от строки $S$ для индекса $j$.
Это приводит нас к следующему алгоритму: пусть $\rm{\pi}[ j ]$ — префикс-функция от строки $S[ 0, m - 1 ]$ для индекса $j$. Тогда после сдвига мы можем возобновить сравнения с места $T[ i + j ]$ и $S[ \rm{\pi}[ j ] ]$ без потери возможного местонахождения образца. Можно показать, что таблица $\rm{\pi}$ может быть вычислена (амортизационно) за $\Theta( m )$ сравнений перед началом поиска. А поскольку строка $T$ будет пройдена ровно один раз, суммарное время работы алгоритма будет равно $\Theta(m + n)$, где $n$ — длина текста $T$.
Реализация на Python
# КМП-поиск подстроки: время O(n + m), память O(m), n - длина текста, m - длина образца
def prefix_function(pattern: str) -> list[int]:
"""Для каждого i: длина наибольшего собственного префикса pattern[0..i], совпадающего с суффиксом."""
pi = [0] * len(pattern)
matched = 0 # длина совпавшего префикса образца
for i in range(1, len(pattern)):
while matched > 0 and pattern[i] != pattern[matched]:
matched = pi[matched - 1]
if pattern[i] == pattern[matched]:
matched += 1
pi[i] = matched
return pi
def kmp_search(text: str, pattern: str) -> int:
"""Индекс первого вхождения pattern в text или -1, если вхождения нет."""
if not pattern:
return 0
pi = prefix_function(pattern)
matched = 0 # длина совпавшего префикса образца
for i, symbol in enumerate(text):
while matched > 0 and symbol != pattern[matched]:
matched = pi[matched - 1]
if symbol == pattern[matched]:
matched += 1
if matched == len(pattern):
return i - len(pattern) + 1
return -1
if __name__ == "__main__":
print("pi для abacaba:", prefix_function("abacaba"))
print("abra в abracadabra:", kmp_search("abracadabra", "abra"))
print("cad в abracadabra:", kmp_search("abracadabra", "cad"))
print("xyz в abracadabra:", kmp_search("abracadabra", "xyz"))
Реализация на Rust
// КМП-поиск подстроки: время O(n + m), память O(m), n - длина текста, m - длина образца
// Префикс-функция: pi[i] - длина наибольшего собственного префикса pattern[0..=i],
// который одновременно является суффиксом этого отрезка.
pub fn prefix_function(pattern: &[u8]) -> Vec<usize> {
let mut pi = vec![0; pattern.len()];
let mut matched = 0; // длина совпавшего префикса образца
for i in 1..pattern.len() {
while matched > 0 && pattern[i] != pattern[matched] {
matched = pi[matched - 1];
}
if pattern[i] == pattern[matched] {
matched += 1;
}
pi[i] = matched;
}
pi
}
// Индекс первого вхождения pattern в text или None, если вхождения нет.
pub fn kmp_search(text: &[u8], pattern: &[u8]) -> Option<usize> {
if pattern.is_empty() {
return Some(0);
}
let pi = prefix_function(pattern);
let mut matched = 0; // длина совпавшего префикса образца
for (i, &symbol) in text.iter().enumerate() {
while matched > 0 && symbol != pattern[matched] {
matched = pi[matched - 1];
}
if symbol == pattern[matched] {
matched += 1;
}
if matched == pattern.len() {
return Some(i + 1 - matched);
}
}
None
}
fn main() {
println!("pi для abacaba: {:?}", prefix_function(b"abacaba"));
println!("abra в abracadabra: {:?}", kmp_search(b"abracadabra", b"abra"));
println!("cad в abracadabra: {:?}", kmp_search(b"abracadabra", b"cad"));
println!("xyz в abracadabra: {:?}", kmp_search(b"abracadabra", b"xyz"));
}Реализация на C++
// КМП-поиск подстроки: время O(n + m), память O(m), n - длина текста, m - длина образца
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>
// Префикс-функция: pi[i] - длина наибольшего собственного префикса pattern[0..i],
// который одновременно является суффиксом этого отрезка.
std::vector<std::size_t> prefix_function(const std::string& pattern) {
std::vector<std::size_t> pi(pattern.size(), 0);
std::size_t matched = 0; // длина совпавшего префикса образца
for (std::size_t i = 1; i < pattern.size(); ++i) {
while (matched > 0 && pattern[i] != pattern[matched]) {
matched = pi[matched - 1];
}
if (pattern[i] == pattern[matched]) {
++matched;
}
pi[i] = matched;
}
return pi;
}
// Индекс первого вхождения pattern в text или -1, если вхождения нет.
std::ptrdiff_t kmp_search(const std::string& text, const std::string& pattern) {
if (pattern.empty()) {
return 0;
}
const std::vector<std::size_t> pi = prefix_function(pattern);
std::size_t matched = 0; // длина совпавшего префикса образца
for (std::size_t i = 0; i < text.size(); ++i) {
while (matched > 0 && text[i] != pattern[matched]) {
matched = pi[matched - 1];
}
if (text[i] == pattern[matched]) {
++matched;
}
if (matched == pattern.size()) {
return static_cast<std::ptrdiff_t>(i + 1 - matched);
}
}
return -1;
}
int main() {
std::cout << "pi для abacaba:";
for (std::size_t value : prefix_function("abacaba")) {
std::cout << ' ' << value;
}
std::cout << '\n';
std::cout << "abra в abracadabra: " << kmp_search("abracadabra", "abra") << '\n';
std::cout << "cad в abracadabra: " << kmp_search("abracadabra", "cad") << '\n';
std::cout << "xyz в abracadabra: " << kmp_search("abracadabra", "xyz") << '\n';
return 0;
}