Задача про мавп і нескінченність

Всім відомо, що якщо посадити мавпу за друкарську машинку і змусити її вічно випадково стукати по клавішах, то, рано чи пізно, вона надрукує «Війну і мир», збірка праць Піфагора та навіть статтю, яку ви зараз читаєте.

Приголомшливий факт, але ще цікавіше спробувати зрозуміти, скільки ж часу їй знадобиться для конкретного набору тексту. А вам очевидно, що рядок «abc» набирати набагато швидше ніж «aaa»? Рішенням цієї задачі і присвячений цей пост. Попутно пояснюється префікс функція і її властивості.
Зрозуміло, що час, витрачений мавпою на набір конкретного тексту — це деяка випадкова величина. Тому логічно запитати про її математичне сподівання.
Формальна постановка завдання
Дано рядок s, що складається з прописних латинських букв (a-z). Потрібно знайти мат. сподівання кількості випадкових натискань на клавіші до того, як буде набрана вся рядок s, якщо всі символи, що набираються рівноймовірно (з ймовірністю 1/26).
Код рішенняЩоб зрозуміти, чому це працює і що це за функція Pi() потрібно прочитати всю статтю :(.
string s; //рядок, яку набирає мавпа
int n = s.length();
vector<int> p = Pi(s);
vector<long double> pow(n+1);
pow[0] = 1;
int i;
for (i = 1; i < = n; i++) {
pow[i] = pow[i-1]*26;
}
long double ans = 0;
for (i = n; i>0; i = p[i-1]) {
ans += pow[i];
}
cout << ans;

Префікс функція
Саме ця функція допоможе нам вирішити поставлену задачу. Префікс функція була введена Д. Батогом і М. Праттом (і паралельно Д. Моррісом) для їх знаменитого алгоритму пошуку підрядка в рядку (алгоритм КМП). Префікс функція для рядка s повертає довжину найдовшого власного префікса рядка, який також є її суфіксом.
Префікси і суфіксиПрефікс — це просто початок рядка, якщо відкинути скільки символів з кінця. Так у рядки "aba" є 4 префікса: "" (порожній рядок), "a", "ab" і "aba". Суфікс — теж саме, але символи видаляються з початку. При цьому деякі суфікси і префікси можуть збігтися. Для рядка "aba" є 3 таких префікса-суфікс: "","a" і "aba" (четвертий суфікс "ba" не збігається з префіксом "ab"). Суфікс або префікс називається власним, якщо він коротший всій рядка.
Формально кажучи: \pi(s) = max\{ k \,|\, 0\le k &amp;lt; |s|,\, pref_k(s) = suf_k(s)\}
Де prefk (s) — це префікс довжини k рядка s, sufk(s) — це суфікс довжини k рядка s.
Як в алгоритмі КМП, так і в інших застосуваннях, набагато корисніше розглядати префікс функцію відразу для всіх префіксів даного рядка. Так, звучить страшно — для кожного префікса потрібно знайти найбільший власний префікс, який збігається з суфіксом префікса. Але насправді все просто:
\pi_s(k) = \pi(pref_k(s)),\, 1\le k \le |s|
Така розширена префікс функція корисна насамперед тим, що її простіше обчислювати, ніж просто \pi(s). Нижче показано значення \pi_s(k)s=«ababac».
k: 1 2 3 4 5 6
s: a b a b a c
P(i): 0 0 1 2 3 0
Обчислення префікс функції

Код обчислення
vector<int> Pi(string s) {
int n = s.length();
vector<int> p(n);
p[0] = 0;
for (int i = 1; i < n; i++) {
int j = p[i-1]; 
while (j > 0 && s[i] != s[j]) { 
j = p[j];
}
if (s[i] == s[j]) j++;
p[i] = j;
} 
return p;
}

Швидке, за O(N), обчислення префікс функції засноване на двох простих спостереженнях.
(1) Щоб отримати префікс суфікс для позиції k треба взяти якийсь префікс суфікс для позиції k-1 і дописати до нього в кінець символ на позиції k.
(2) Всі префікси-суфікси рядка s довжини n можна отримати як \pi_s(n),\, \pi_s(\pi_s(n)),\, \pi_s(\pi_s(\pi_s(n)))і так далі, поки чергове значення не стане рівним 0. Це властивість можна перевірити на рядку «abacaba». Тут \pi_s(7)=3,\, \pi_s(3)=1,\, \pi_s(1)=0, що відповідає всім префиксам-суфіксів («aba», «a» і «»). Так виходить тому, що максимальний префікс суфікс має довжину \pi_s(n). Наступний по довжині префікс суфікс буде коротше. Але оскільки перший префікс суфікс зустрічається як на початку, так і на кінці рядка s, то наступний префифкс-суфікс буде довжелезним префіксом-суфіксом у першому префіксі-суфіксі.
Тому для побудови префікс функції для позиції i досить проитерироваться починаючи зі значення префікс функції в попередній позиції поки продовження суфікса новим символом не буде також і префіксом (для цього треба перевірити тільки один новий символ). Такий алгоритм виконується за лінійний час, тому що значення префікс функції щоразу збільшується максимум на 1, тому воно не може зменшиться більш ніж n разів, а значить, вкладений цикл сумарно виконається не більше ніж n разів.
Кінцевий автомат KMP
Наступний математичний об'єкт, необхідний у вирішенні поставленого завдання — це кінцевий автомат, що приймає рядка, що закінчуються на задану рядок s. Цей автомат використовується в інший, менш відомої модифікації алгоритму Батога-Морисса-Пратта. У цій версії алгоритму будується кінцевий автомат, який приймає всі рядки, які закінчуються на задану рядок (шаблон). Потім автомату передається рядок-текст. Кожен раз, коли автомат приймає переданий йому текст, знайдено чергове входження шаблону. Саме цей автомат і допоможе нам вирішити задачу про мавпу за печатоной машинкою.
Що таке кінцевий автоматКінцевий автомат — це математичний об'єкт, який найпростіше представити собі як деяку коробку у якої є якийсь внутрішній стан. Спочатку коробка знаходиться в початковому стані. У коробку можна вводити рядки, по одному символу за раз. Після кожного символу коробка змінює свій стан, при чому в залежності від поточного стану і введеного символу. Так само деякі стану є хорошими (математичний термін — кінцеві стани). Кажуть, що автомат приймає рядок, якщо після згодовування йому цього рядка символ за символом, автомат знаходиться в хорошому стані.
Для визначення КА потрібно визначити початковий стан, хороші стану і функцію переходу — для кожного стану і символу потрібно вказати новий стан, в який автомат перейде. Зручно малювати автомат як повний орієнтований граф, де вершини — це стостояния, а на кожному ребрі написаний рівно один символ. З кожної вершини має бути рівно одне ребро з кожним символом. Тоді для обробки якийсь рядка треба просто перейти по ребрах з символами з цього рядка. Якщо шлях закінчився в кінцевому стані, то автомат таку рядок приймає.
Для побудови цього автомата ми будемо використовувати вже відому нам префікс функцію.
В автоматі буде n+1 стан, пронумеровані від 0 n. Стан k відповідає збігом останніх k набраних символів з префіксом шаблону довжини k (Якщо ми шукаємо рядок «abac» то нам від поточного тексту цікаво тільки, що там на кінці: «abac», «ава», «ab», «a» або щось на одного. Цієї інформації достатньо щоб отримати такуюже після дописування одного символу). Стан 0 буде початковим, а стан n — кінцевим. Іноді може бути плутанина: наприклад, для терміни «ababccc» при скормленой автамату рядку «zzzabab» можна вибрати як стан 2, так і 4. Але, щоб не втрачати потрібну інформацію про набраному тексті, ми завжди будемо вибирати найбільшу стан.
приклад кінцевого автомата KMPОсь автомат для рядка "ababac". Для прикладу алфавіт складається лише з символів 'a'-'c'. Паралельні ребра об'єднані для наочності. Насправді кожному ребру відповідає тільки один символ. Початковий стан — 0, кінцеве — 6.


Нескладно переконатися, що будь-який шлях з стану 0 у стан 6, яким би складним він не був, обов'язково закінчується на рядок "ababac". І навпаки, будь-такий шлях обов'язково закінчиться в змозі 6.
Код побудови кінцевого автомата
string s; //вихідна рядок.
int n = s.length();
vector < vector < int> > nxt(n+1, vector<int>(256)); 
// функція переходу nxt[стан][символ] == новий стан
vector<int> p = Pi(s); // Префікс функція. См. код вище
nxt[0][s[0]] = 1; //єдиний перехід зі стану 0 в 0.
for (int i = 1; i < = n; i++) {
for (int c = 0; c < 256; c++)
nxt[i][c] = nxt[p[i-1]][c]; //p[] індексується з нуля, тому потрібно -1
if (i < n) nxt[i][s[i]] = i+1;
}

Зверніть увагу, як будуються переходи. Для розрахунку переходів зі стану i ми розглядаємо 2 варіанти. Якщо новий символ — це s[i] — то перехід буде в стан i+1. Тут все очевидно: якщо було збіг i символів — то додавши наступний символ рядка s ми збільшимо довжину збігу 1. Якщо ж символ не збігається, то ми просто копіюємо переходи з стану \pi_s(i). Чому? Перехід в цьому випадку буде точно в стан з номером ≤i. Значить після переходу ми забудемо частину інформації про набраному тексті. Можна зробити це перед переходом. Самий мінімум, що ми можемо стерти, це прикинутися що насправді зараз стан не i, а \pi_s(i). Це як в тому прикладі вище, можна було вважати, що текст закінчується на «abab» або «ab». Якщо з «abab» ніяких переходів немає — можна використовувати переходи з «ab».
Рішення
Тепер ми готові вирішити поставлену задачу.
Побудуємо для рядка s автомат KMP. Оскільки всі символи, що набираються мавпою випадково, нам не важливі самі символи, а тільки ребра в графі переходів. Завдання можна переформулювати так: знайти мат. сподівання кількості переходів у випадковому блуканні зі стану 0 поки не досягнуто стан n.
Логічно в такій постановці ввести змінні: Ek, 0≤k≤n — матожидание кількості переходів до досягнення стану n. E0 буде відповіддю до вихідної задачі. Нехай Z — це множина допустимих символів (алфавіт). Можна скласти систему рівнянь:
E_n = 0
E_k = 1 + \frac{1}{|Z|}\sum_{c \in Z}{E_{nxt[k][c]}}, k=0..n-1
Рівняння (1) означає, що досягнувши стану n випадкове блукання зупиняється.
Для будь-якого іншого стану буде зроблено якийсь перехід, тому в рівнянні (2) є доданок 1. Другий доданок — це сума по всім можливим варіантам, помноженим на ймовірність цих варіантів. Всі ймовірності однакові — тому вона винесена за знак суми.
Ось вже є рішення задачі за O(n^3): побудовану систему лінійних рівнянь можна розв'язати методом Гаусса. Але якщо трохи подивитися на цю систему і згадати, що є префікс функція, тобто рішення набагато простіше і швидше.
Згадаймо побудова кінцевого автомата. (Для простоти далі замість \pi_sя буду використовувати просто \pi). Переходи з стану k майже повністю збігаються з переходами з стану \pi(k). Відмінність у переході тільки по символу s[k-1]. Тому праві частини рівнянь (2) для станів k і \pi(k)відрізняються тільки одним доданком. В рівнянні для \pi(k)варто E_{nxt[\pi(k)][s[k-1]]}замість E_{nxt[k][s[k-1]]}в рівнянні для k. При чому nxt[k][s[k-1]]=k+1. Використовуючи цей факт можна переписати рівняння (2):
E_k = E_{\pi(k)} + \frac{1}{|Z|}(E_{k+1}-E_{nxt[\pi(k)][s[k-1]]})
Тепер треба зробити ще одне спостереження. Виявляється
nxt[\pi(k)[s[k-1]] = \pi(k+1)
тобто щоб знайти префікс функцію для якогось стану, треба взяти префікс функцію від попереднього стану і перейти звідти по символу, провідному в наступний стан.
Дійсно, якщо розглянути стан \pi(k), то воно відповідає рядку, закінчується на символ s[k-1]. Значить туди є переходи з цього символу. Розглянемо найбільше багатство, з якого такий перехід є, але яке має номер < k. Якщо після переходу по символу s[k-1] ми отримали якийсь суфікс pref_k(s), то до переходу це був суфікс pref_{k-1}(s). Оскільки це було саме праве такий стан, то воно відповідає максимальному префікса-суффиксу pref_{k-1}(s), а значить воно має номер \pi(k-1). Ось ми і отримали цей дивовижний і корисний факт.
Тоді (3) перетвориться в:
E_k = E_{\pi(k)} + \frac{1}{|Z|}(E_{k+1}-E_{\pi(k+1)})
Або по-іншому:
|Z| (E_k - E_{\pi(k)}) =(E_{k+1}-E_{\pi(k+1)})
З обох сторін від знака рівності тут від'ємні числа (логічно, що чим більше k, тим менше Ek). Помножимо обидві частини на -1.
|Z| (E_{\pi(k)}-E_k) =E_{\pi(k+1)}-E_{k+1}
Але (4) справедливо тільки для k>0. Для k=0 можна явно виписати рівняння (2), адже тільки один з |Z| переходів веде в стан 1, а всі інші повертаються в стан 0:
E_0 = 1 + \frac{1}{|Z|}E_1 + \frac{|Z|-1}{|Z|}E_0
Тепер зберемо всі змінні зліва, домножим рівняння на |Z| і замінимо 0=\pi(1)(префікс функція для одного символу завжди дорівнює 0, т.к. непустих власних префіксів у одного символу немає):
E_{\pi(1)} - E_1 = |Z|
Я дозволю собі повторити рівняння (1), (4) і (5), так як вони складають систему, яку ми тепер вирішимо аналітично:
E_{\pi(1)} - E_1 = |Z| \\
|Z| (E_{\pi(k)}-E_k) =E_{\pi(k+1)}-E_{k+1},\, k=1..n-1 \\
E_n = 0
Підставляючи перше рівняння в ліву частину другого при k=1, потім k=2 і т. д. отримуємо:
E_{\pi(k)} - E_k = |Z|^k ,\, k=1..n
Ось вже майже готове рішення: тепер розглянемо (6) при k=n і згадаємо, що E_n = 0, отримуємо:
E_{\pi(n)} = |Z|^n
Підставляємо це значення в (6) при k = \pi(n)— отримуємо:
E_{\pi(\pi(n))} = |Z|^n + |Z|^{\pi(n)}
Аналогічно, отримуємо:
E_{\pi(\pi(\pi(n)))} = |Z|^n + |Z|^{\pi(n)} + |Z|^{\pi(\pi(n))}
І так можна продовжувати до того часу, поки не отримаємо вираз для E_0, що, до речі, і є відповіддю до задачі. Позначимо \pi^kзастосовану k раз поспіль функцію \pi, тоді:
E_0 = \sum_{k:\pi^k(n) &amp;gt; 0}|Z|^k
Таким чином, ми отримали рішення задачі за O(n): побудувати префікс функцію до рядка s і итерироваться по ній починаючи з n поки не досягнемо 0, попутно складаючи ступеня |Z| рівні поточної довжині префікса. Це і є те саме рішення, наведене на початку статті.
Дивлячись на (*) стає зрозуміло, чому рядок «aaa» набрати складніше ніж «abc», адже у «aaa» тільки третя ітерація \piдорівнює нулю, а у другого рядка взагалі немає пустих префіксів рівним суфіксів і \piвідразу дає нуль.
Зауваження
Префікс функція і автомат КМП дуже корисні інструменти для роботи з рядками. Якщо у шановних читачів є інтерес, то я можу розібрати вирішення інших завдань. Про будь опечатки прошу повідомляти в лічку, спасибі.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.