Самоподобные строки

Рекурсивное построение, поиск символа, подсчёт — фирменная тема ИТМО

Строка строится по правилу подстановки: на каждом шаге каждый символ заменяется на фрагмент (или между символами вставляется новый). Строка растёт экспоненциально, но сохраняет регулярную структуру.

Три типовых конструкции

тип 1: подстановка
// Туэ-Морс: A → AB, B → BA
S₀ = A
S₁ = AB
S₂ = ABBA
S₃ = ABBABAAB
// длина: L(n) = 2ⁿ

тип 2: вставка
// Между каждой парой вставляется новый символ
S₀ = AB
S₁ = ACB       // вставили C
S₂ = ADCDB     // вставили D между каждой парой
// длина: L(n+1) = 2L(n) − 1

тип 3: конкатенация
// S(n+1) = S(n) + X + S(n)
S₀ = A
S₁ = ABA
S₂ = ABACABA
S₃ = ABACABADABACABA
// длина: L(n+1) = 2L(n) + 1

На ИТМО правило всегда дают явно. Задача — разглядеть структуру и построить рекурсию.

Почти всегда длина подчиняется линейной рекурсии:

Замкнутая формула

вывод
// Пусть T(n) = L(n) + c/(a−1). Тогда T(n+1) = a·T(n)
L(n) = (L(0) + c/(a−1)) × aⁿ − c/(a−1)   (при a ≠ 1)

Справочник типовых рекурсий

Это ключевая техника для задач ИТМО. Позиция p огромная (до 10⁹), но символ находится за O(N) шагов.

Алгоритм для типа «конкатенация»: S(n) = S(n−1) + X + S(n−1)

алгоритм
1. Вычислить L(0), L(1), ..., L(N) — найти мин. N: L(N) ≥ p
2. Определить, куда попадает p:
   • p ≤ L(N−1)     → левая копия S(N−1), оставить p
   • p = L(N−1) + 1 → разделитель X (ответ!)
   • p > L(N−1) + 1 → правая копия: p' = p − L(N−1) − |X|
3. Уменьшить N на 1, повторять с шага 2

Алгоритм для типа «вставка между парами»

алгоритм
// В S(n) нечётные позиции = символы S(n−1)
// Чётные позиции = вставленный символ шага n

1. p чётное   → вставленный символ шага n (ответ!)
2. p нечётное → спуск: p' = (p+1)/2, n' = n−1

Алгоритм для типа «подстановка» (Туэ-Морс)

Туэ-Морс
// S(n) = [первая половина = S(n−1)] [вторая = S(n−1) с A↔B]

1. p ≤ L(n)/2 → левая половина, без инверсии
2. p > L(n)/2 → правая половина, инверсия A↔B, p' = p − L(n)/2
3. Считаем число инверсий. Если нечётное — меняем ответ.

// Пример: S₃[5], L(3)=8
p=5 > 4 → правая, инверсия, p'=1, n=2
p=1 ≤ 2 → левая, n=1
p=1 ≤ 1 → левая, n=0
S₀[1] = A, инверсий: 1 (нечёт) → B ✓

Во всех случаях строку целиком строить не нужно. Спуск работает за O(log p) шагов.

Вторая частая подзадача: сколько раз символ X встречается в S(n)?

метод
// Правило: A → α, B → β
// count_A(α) = число A в строке α

a(n+1) = count_A(α) × a(n) + count_A(β) × b(n)
b(n+1) = count_B(α) × a(n) + count_B(β) × b(n)

// Пример: A→ABA (2A, 1B), B→B (0A, 1B)
a(n+1) = 2·a(n) + 0·b(n) = 2a(n)
b(n+1) = 1·a(n) + 1·b(n) = a(n) + b(n)

n:  0  1  2   3
a:  1  2  4  8
b:  0  1  3  7
L:  1  3  7  15

На ИТМО матричную форму обычно не требуют — достаточно рекурсии.

Условие (в стиле финала ИТМО)

S₀ = «AB». На каждом шаге между каждой парой соседних символов вставляется новый: на шаге 1 — C, на шаге 2 — D, на шаге k — буква с номером k+2. Найти символ на позиции 1000 в S₁₀.

шаг 1: длины
L(n+1) = 2L(n) − 1
L: 2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025
// L(10) = 1025 ≥ 1000 ✓

шаг 2: спуск
// Нечётные позиции → символы S(n−1)
// Чётные позиции → вставленный символ шага n

p = 1000, n = 10
1000 чётное → символ шага 10 → буква #12 = «L»
// Готово за ОДИН шаг!

// А если бы p = 999:
// 999 нечётное → p' = 500, n = 9
// 500 чётное → символ шага 9 → буква #11 = «K»