1. Теория. DP на строках

«Слова состоят из букв, но смысл рождается лишь в их неизменном порядке».
— Брайан Керниган

Строковое динамическое программирование — специализированный и один из самых востребованных разделов алгоритмической инженерии. В отличие от числовых массивов и геометрических матриц, строки в современных языках программирования обладают уникальной природой: они неизменяемы (immutable), состоят из байтовых последовательностей (UTF-8) и требуют аккуратного обращения с памятью.

В архитектуре высоконагруженных систем строковое DP лежит в фундаменте:

• Систем контроля версий (Git diff, 3-way merge, алгоритм Майерса).
• Движков полнотекстового поиска и нечеткого матчинга (Elasticsearch, Lucene, BLEVE).
• Биоинформатики и геномики (сравнение ДНК/РНК последовательностей, BLAST).
• Лексических анализаторов, парсеров протоколов и компиляторов регулярных выражений.

1. Анатомия строк в Go: StringHeader и strings.Clone

Чтобы писать строковые алгоритмы с максимальной производительностью, необходимо понимать внутреннее устройство строк в Go runtime.
Строка в Go — это не массив и не объект в стиле Java String. Это компактная 16-байтная структура:

type stringStruct struct {
    str unsafe.Pointer // Указатель на непрерывный байтовый массив в куче/сегменте данных
    len int            // Длина строки строго в БАЙТАХ
}

Строка является неизменяемым представлением (read-only view) над базовым массивом байт.

flowchart LR
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    subgraph Memory["Базовый массив в куче (10 МБ HTTP Payload)"]
        Raw["[ H e a d e r :   T o k e n ... 10 MB payload ... ]"]:::process
    end

    Sub["Срез: token := payload[:10]<br/>(16 байт StringHeader)"]:::warning --> Raw
    GC["Garbage Collector: ЗАБЛОКИРОВАН!<br/>10 МБ удерживаются 16-байтным заголовком"]:::error -.-> Raw
  

2. Mechanical Sympathy: Байты против Рун (UTF-8)

В Go индексация s[i] обращается к $i$-му байту, а не к символу:

1. ASCII-текст (латиница, цифры, код): 1 символ = 1 байт. Индексация s[i] занимает ровно 1 такт CPU ($O(1)$ без накладных расходов).
2. UTF-8 (кириллица, китайские иероглифы, эмодзи): 1 символ (руна) занимает от 1 до 4 байт.

s := "Привет"
println(len(s))    // 12 байт!
println(s[0])      // 208 (первый байт префикса UTF-8 для 'П')

Если алгоритм DP манипулирует многоязычным текстом, прямое обращение к байтам разорвет символы на части. В таких сценариях перед запуском матрицы строки приводятся к срезу рун:

runes := []rune(s) // O(N) по времени и памяти, но 100% Unicode-safety

3. Таксономия паттернов строкового DP

Все строковые задачи динамического программирования делятся на три фундаментальных класса:

flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    Root["Строковое DP"]:::entry --> P1["1. Сравнение двух строк<br/>(2D Матрицы)"]:::process
    Root --> P2["2. Палиндромы и интервалы<br/>(Диагональное 2D DP)"]:::process
    Root --> P3["3. Парсинг и матчинг<br/>(1D DP + Matchers)"]:::process

    P1 --> E1["LCS, Edit Distance, Interleaving<br/>Сложность: O(M * N)"]:::success
    P2 --> E2["Longest Palindromic Subsequence<br/>Сложность: O(N^2)"]:::warning
    P3 --> E3["Word Break, Regex Matching, Wildcard<br/>Сложность: O(N * K)"]:::success
  

Паттерн 1: Сопоставление двух строк (LCS, Edit Distance)

Матрица $dp[i][j]$ связывает префикс $S[0 \dots i-1]$ с префиксом $T[0 \dots j-1]$.
Переход зависит от совпадения крайних символов: $S[i-1] == T[j-1]$.

Паттерн 2: Интервальное DP на палиндромах

Состояние $dp[i][j]$ отвечает за подстроку $S[i \dots j]$.
Переход разворачивается изнутри наружу: подстрока является палиндромом, если $S[i] == S[j]$ и внутренняя часть $dp[i+1][j-1]$ — палиндром. Обход выполняется по возрастанию длины подстроки.

Паттерн 3: Префиксный парсинг (Word Break)

Одномерный срез $dp[i]$ хранит булев флаг: можно ли разбить префикс $S[0 \dots i-1]$ на токены из словаря.

4. Архитектура и System Design: Алгоритм Майерса (Myers Diff) в Git

Почему git diff для двух файлов по 100 000 строк не падает по таймауту, хотя классический LCS требует $O(N \cdot M) = 10^{10}$ операций и десятки гигабайт памяти?

В 1986 году Юджин Майерс (Eugene Myers) предложил алгоритм, ставший мировым стандартом в системах контроля версий (GNU diff, Git):

1. Жадный обход «змей» (Snakes): В исходном коде программ 90–99% строк не меняются между коммитами. Совпадающие блоки символов образуют диагональные отрезки в матрице переходов.
2. Параметризация по числу правок $D$: Алгоритм ищет кратчайший путь на графе редактирования с помощью оптимизированного BFS, где сложность составляет не $O(N \cdot M)$, а:
   $$O\Big((N + M) \cdot D\Big)$$
   Где $D$ — реальное количество измененных строк! Если в файле из 50 000 строк изменилось 5 строк ($D = 5$), diff выполняется за доли миллисекунды.

5. Вопросы для собеседования

Итог

1. Модель памяти: Строка в Go — это StringHeader (16 байт). Для предотвращения утечек при удержании срезов используйте strings.Clone (Go 1.20+).
2. Байты vs Руны: ASCII обрабатывается байтами на полной скорости кэша L1; Unicode требует явной конвертации в []rune.
3. Разделение сложности: Полный 2D DP подходит для коротких строк. Для мегабайтных текстов и файлов применяются эвристики и алгоритм Майерса $O((N+M) \cdot D)$.

В следующей лекции мы разберем математическую дуальность двух ключевых строковых задач — LCS и Edit Distance: 2. LCS и edit distance.