Хэш сумма подстроки

1. **Что такое хэш-сумма подстроки?**
Хэш-сумма подстроки — это числовое значение, которое представляется результатом применения хэш-функции к какой-либо части строки. Это позволяет быстро сравнивать части строки, не проверяя их символ за символом.

### 2. **Как работает этот подход?**
Алгоритм Рабина-Карпа (Rabin-Karp algorithm) — это классический пример использования хэш-функции для поиска подстрок. Он использует хэш-суммы для быстрого сравнения подстрок и позволяет проверить, содержится ли подстрока в строке за время \(O(n + m)\), где \(n\) — длина строки, а \(m\) — длина подстроки. При этом на основе хэш-сумм можно быстро находить совпадения.

### 3. **Алгоритм Рабина-Карпа**
Рассмотрим базовый подход:

- Для каждой подстроки вычисляется хэш-сумма.
- Для поиска подстроки в строке вычисляется хэш-сумма подстроки и сравнивается с хэш-суммами всех возможных подстрок строки.

Для вычисления хэш-суммы строки можно использовать полиномиальный хэш:
\[
H(s) = (s_0 \cdot b^0 + s_1 \cdot b^1 + s_2 \cdot b^2 + ... + s_{n-1} \cdot b^{n-1}) \mod p
\]
где \(s_i\) — это i-й символ строки, \(b\) — это основание, а \(p\) — большое простое число для минимизации коллизий.

Когда мы вычисляем хэш-сумму для каждой подстроки, при поиске мы просто сравниваем хэш-суммы, что делает этот процесс намного быстрее, чем стандартное побуквенное сравнение.

### 4. **Удаленные подстроки**
В случае, когда вам нужно использовать несколько подстрок, которые могут быть удалены друг от друга, алгоритм может быть адаптирован для вычисления хэш-сумм для этих подстрок в различных позициях. Вы можете:
- Использовать технику "Sliding Window" для вычисления хэш-сумм в скользящих окнах (передвигая окно по строке).
- Хранить хэш-суммы всех подстрок в радужной таблице или списке для дальнейшего поиска.

### 5. **Использование радужных таблиц**
Радужные таблицы — это заранее вычисленные таблицы для быстрого восстановления хэш-сумм. В контексте поиска подстрок они могут быть использованы для того, чтобы "расшифровывать" хэш-сумму в подстроку.

Для поиска подстроки вы можете использовать радужные таблицы, чтобы по хэш-сумме искать возможные исходные строки или подстроки в строках.

**Пример работы с радужными таблицами:**
- Для каждой возможной длины подстроки вы строите таблицу с хэшами.
- При поиске подстроки вы используете хэш и быстро ищете соответствующую подстроку в таблице.

### 6. **Реализация**
Пример на Python для базового алгоритма Рабина-Карпа:

```python
def rabin_karp_search(text, pattern):
n = len(text)
m = len(pattern)
p = 101 # Простое число для хэширования
b = 256 # Основание для хэширования (можно использовать любой символ)

# Вычисление хэш-суммы для шаблона и первой подстроки текста
pattern_hash = 0
text_hash = 0
for i in range(m):
pattern_hash = (pattern_hash * b + ord(pattern[i])) % p
text_hash = (text_hash * b + ord(text[i])) % p

# Сила основания для скользящего окна
b_power_m = pow(b, m - 1, p)

# Сканирование текста
for i in range(n - m + 1):
# Если хэш-сумма совпадает, проверяем на реальное совпадение
if pattern_hash == text_hash and text[i:i+m] == pattern:
print(f"Pattern found at index {i}")

# Сдвигаем хэш-сумму окна
if i < n - m:
text_hash = (text_hash - ord(text[i]) * b_power_m) * b + ord(text[i + m])
text_hash %= p

# Пример использования
text = "ababcababcabc"
pattern = "abc"
rabin_karp_search(text, pattern)
```
Этот код реализует поиск подстроки с помощью хэш-функции (алгоритм Рабина-Карпа) для строки **text** и шаблона **pattern**.