🧵 Алгоритми върху Низове (String Algorithms)
Ефективната обработка на текст е ключова област. Стандартното търсене (std::string::find) е \(O(N \cdot M)\) в най-лошия случай, което е бавно. Специализираните алгоритми постигат \(O(N + M)\).
1. Полиномно Хеширане (Rolling Hash)
Най-гъвкавият метод. Превръщаме низовете в числа, така че сравнението да става за \(O(1)\). Формула за хеш на низ \(S\): \(H(S) = (S[0] \cdot P^0 + S[1] \cdot P^1 + \dots + S[n-1] \cdot P^{n-1}) \pmod M\)
- \(P\): Основа (напр. 31, 53, или случайно число > размера на азбуката).
- \(M\): Голямо просто число (напр. \(10^9 + 7\)).
Rolling Hash свойство
Можем да изчислим хеша на всеки подниз \(S[i \dots j]\) за \(O(1)\), ако сме прекалкулирали префиксите: \(Hash(i, j) = (H[j] - H[i-1]) \cdot P^{-i} \pmod M\) Вместо деление с \(P^i\), обикновено умножаваме дясната страна на равенството, за да избегнем модулярно обратно.
Двоен Хеш: За да избегнем колизии (различни низове с еднакъв хеш), използваме две двойки \((P_1, M_1)\) и \((P_2, M_2)\). Вероятността за колизия става нищожна.
Пълна имплементация:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class StringHash {
const long long P = 31;
const long long M = 1e9 + 7;
vector<long long> hash_val, pow_p;
int n;
public:
StringHash(const string& s) {
n = s.size();
hash_val.resize(n + 1, 0);
pow_p.resize(n + 1, 1);
for (int i = 0; i < n; i++) {
hash_val[i + 1] = (hash_val[i] + (s[i] - 'a' + 1) * pow_p[i]) % M;
pow_p[i + 1] = (pow_p[i] * P) % M;
}
}
// Хеш на подниз [l, r]
long long getHash(int l, int r) {
long long result = (hash_val[r + 1] - hash_val[l] + M) % M;
return result;
}
// Сравняване на два поднизове
bool equals(int l1, int r1, int l2, int r2) {
int len1 = r1 - l1 + 1;
int len2 = r2 - l2 + 1;
if (len1 != len2) return false;
long long h1 = getHash(l1, r1);
long long h2 = getHash(l2, r2);
// Нормализиране за сравнение
if (l1 < l2) {
h1 = (h1 * pow_p[l2 - l1]) % M;
} else {
h2 = (h2 * pow_p[l1 - l2]) % M;
}
return h1 == h2;
}
};
int main() {
string s = "abracadabra";
StringHash sh(s);
// Проверка дали "abra" се среща на позиция 0 и 7
cout << "Подниз [0,3] == [7,10]: "
<< sh.equals(0, 3, 7, 10) << endl;
return 0;
}
Приложения на хеширане:
- Търсене на подниз за \(O(N)\)
- Намиране на най-дълъг общ подниз на два низа
- Проверка за палиндром на всеки подниз
- Rabin-Karp алгоритъм за множество шаблони
2. Алгоритъм на Кнут-Морис-Прат (KMP)
Използва Префиксна функция (\(\pi\)). \(\pi[i]\) е дължината на най-дългия собствен префикс на подниза \(S[0 \dots i]\), който е едновременно и негов суфикс.
Пример: \(S = \text{"ababa"}\) * \(\pi[0]\) ("a") = 0 * \(\pi[1]\) ("ab") = 0 * \(\pi[2]\) ("aba") = 1 ("a") * \(\pi[3]\) ("abab") = 2 ("ab") * \(\pi[4]\) ("ababa") = 3 ("aba")
Приложения на \(\pi\):
- Търсене на подниз: Търсим \(P\) в \(T\). Правим низ \(S = P + \# + T\). Всички позиции, където \(\pi[i] == |P|\), са срещания.
- Минимален период: Дължината на най-малкия период на низ с дължина \(N\) е \(N - \pi[N-1]\) (ако \(N\) се дели на това число).
vector<int> prefix_function(string s) {
int n = s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i-1];
while (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j])
j++;
pi[i] = j;
}
return pi;
}
Търсене на шаблон с KMP:
vector<int> kmp_search(string text, string pattern) {
string combined = pattern + "#" + text;
vector<int> pi = prefix_function(combined);
vector<int> occurrences;
int m = pattern.size();
for (int i = m + 1; i < combined.size(); i++) {
if (pi[i] == m) {
// Намерено съвпадение на позиция i - 2*m
occurrences.push_back(i - 2 * m);
}
}
return occurrences;
}
Намиране на период:
int minimalPeriod(string s) {
int n = s.size();
vector<int> pi = prefix_function(s);
int period_len = n - pi[n - 1];
if (n % period_len == 0) {
return period_len;
}
return n; // Целият низ е период
}
3. Z-Алгоритъм
Изчислява Z-функция. \(Z[i]\) е дължината на най-дългия общ префикс между низа \(S\) и суфикса на \(S\), започващ от \(i\). * \(Z[0]\) обикновено не се дефинира (или е \(N\)). * Аналогично на KMP, позволява търсене на шаблон за линейно време.
Имплементация на Z-алгоритъм:
vector<int> z_function(string s) {
int n = s.size();
vector<int> z(n);
z[0] = n;
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i <= r) {
z[i] = min(r - i + 1, z[i - l]);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
Търсене на шаблон със Z-алгоритъм:
vector<int> z_search(string text, string pattern) {
string combined = pattern + "$" + text;
vector<int> z = z_function(combined);
vector<int> occurrences;
int m = pattern.size();
for (int i = m + 1; i < combined.size(); i++) {
if (z[i] == m) {
occurrences.push_back(i - m - 1);
}
}
return occurrences;
}
Сложност: \(O(N)\) за построяване на Z-масива.
4. Алгоритъм на Манакър (Manacher)
Намира най-дългия палиндром във всяка позиция на низа за \(O(N)\). * Разглежда отделно палиндроми с нечетна дължина (център в символ) и четна дължина (център между символи).
Имплементация:
string preprocess(string s) {
// Добавяме '#' между символите за единен подход
string result = "#";
for (char c : s) {
result += c;
result += '#';
}
return result;
}
vector<int> manacher(string s) {
string t = preprocess(s);
int n = t.size();
vector<int> p(n, 0); // p[i] = радиус на палиндрома центриран в i
int center = 0, right = 0;
for (int i = 0; i < n; i++) {
int mirror = 2 * center - i;
if (i < right) {
p[i] = min(right - i, p[mirror]);
}
// Опит за разширяване
while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
t[i + p[i] + 1] == t[i - p[i] - 1]) {
p[i]++;
}
// Обновяване на центъра
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
}
return p;
}
string longestPalindrome(string s) {
vector<int> p = manacher(s);
int maxLen = 0, centerIndex = 0;
for (int i = 0; i < p.size(); i++) {
if (p[i] > maxLen) {
maxLen = p[i];
centerIndex = i;
}
}
// Превръщаме обратно в оригинален индекс
int start = (centerIndex - maxLen) / 2;
return s.substr(start, maxLen);
}
Приложение: Броене на всички палиндроми
long long countAllPalindromes(string s) {
vector<int> p = manacher(s);
long long count = 0;
for (int radius : p) {
// Всеки радиус дава (radius + 1) / 2 палиндрома
count += (radius + 1) / 2;
}
return count;
}
Сложност: \(O(N)\) време и \(O(N)\) памет.
5. Сравнение
| Алгоритъм | Сложност | Предимства | Недостатъци |
|---|---|---|---|
| Hashing | \(O(N)\) | Лесен код, гъвкав (палиндроми, сравнения) | Вероятност за колизия (макар и малка) |
| KMP | \(O(N)\) | Детерминистичен, полезен за периодичност | Малко по-сложна логика |
| Z-Algo | \(O(N)\) | По-интуитивен за някои задачи от KMP | По-рядко използван |
| Manacher | \(O(N)\) | Най-бърз за палиндроми | Специфичен за една задача |
| Aho-Corasick | \(O(N)\) | Търсене на множество шаблони едновременно | Базиран на Trie (Тема 26) |
6. Aho-Corasick - Многошаблонно търсене
Алгоритъмът на Aho-Corasick разширява KMP за търсене на множество шаблони едновременно. Използва Trie структура с failure links.
struct AhoCorasick {
static const int K = 26; // Размер на азбуката
struct Vertex {
int next[K];
bool leaf = false;
int p = -1; // родител
char pch; // символ към родителя
int link = -1; // failure link
int go[K]; // precomputed transitions
Vertex(int p = -1, char ch = '$') : p(p), pch(ch) {
fill(begin(next), end(next), -1);
fill(begin(go), end(go), -1);
}
};
vector<Vertex> trie;
AhoCorasick() {
trie.emplace_back();
}
void add_string(string const& s) {
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (trie[v].next[c] == -1) {
trie[v].next[c] = trie.size();
trie.emplace_back(v, ch);
}
v = trie[v].next[c];
}
trie[v].leaf = true;
}
int get_link(int v) {
if (trie[v].link == -1) {
if (v == 0 || trie[v].p == 0)
trie[v].link = 0;
else
trie[v].link = go(get_link(trie[v].p), trie[v].pch);
}
return trie[v].link;
}
int go(int v, char ch) {
int c = ch - 'a';
if (trie[v].go[c] == -1) {
if (trie[v].next[c] != -1)
trie[v].go[c] = trie[v].next[c];
else
trie[v].go[c] = v == 0 ? 0 : go(get_link(v), ch);
}
return trie[v].go[c];
}
int search(string text) {
int v = 0;
int count = 0;
for (char ch : text) {
v = go(v, ch);
int temp = v;
while (temp != 0) {
if (trie[temp].leaf) count++;
temp = get_link(temp);
}
}
return count;
}
};
7. Практически задачи
- CSES String Matching: Базова задача за KMP/Z-алгоритъм.
- Codeforces 1200E: Compress Words (Hashing/KMP).
- SPOJ NHAY: Търсене на игла в купа сено.
- CSES Finding Patterns: Aho-Corasick или суфиксни масиви.
- CSES Palindrome Queries: Манакър с модификации.
- Codeforces 126B: Password (KMP за префикс-суфикс).
8. Допълнителни техники
Суфиксен масив (Suffix Array)
Сортиран масив от всички суфикси на низа. Построява се за \(O(N \log N)\) с radix sort или \(O(N \log^2 N)\) с binary lifting.
Суфиксно дърво (Suffix Tree)
Compressed trie от всички суфикси. Може да се построи за линейно време с Ukkonen's algorithm, но е сложен за имплементация.
Longest Common Prefix (LCP)
LCP масивът съдържа дължините на най-дългите общи префикси между съседни суфикси в суфиксния масив. Използва се за много задачи върху поднизове.
🏁 Заключение
Алгоритмите върху низове са основен инструмент в състезателното програмиране. Започнете с хеширане за бързи прототипи, научете KMP за детерминистични решения, и овладейте Aho-Corasick за многошаблонно търсене. Всеки от тези алгоритми има своето приложение и силни страни.