УЛІПО

Французький письменник Жорж Перек (1936–1982) одного разу написав книгу La disparition без використання літери 'e'. Він був членом групи Oulipo (фр. OULIPO, Ouvroir de littérature potentielle), спілки письменників і математиків, які досліджували потенційні можливості мови, вивчаючи відомі й вигадуючи нові штучні літературні обмеження.

Цитата з книги:

Tout avait Pair normal, mais tout s'affirmait faux. Tout avait Fair normal, d'abord, puis surgissait l'inhumain, l'affolant. Il aurait voulu savoir où s'articulait l'association qui l'unissait au roman : stir son tapis, assaillant à tout instant son imagination, l'intuition d'un tabou, la vision d'un mal obscur, d'un quoi vacant, d'un non-dit : la vision, l'avision d'un oubli commandant tout, où s'abolissait la raison : tout avait l'air normal mais…

Перек, напевно, отримав би високий (чи, можливо, низький) бал у наступному конкурсі. Учасникам пропонується написати, навіть беззмістовний, текст, у якому задане «слово» зустрічається якнайменше разів. Журі має програму, яка підраховує кількість входжень цього слова до тексту, таким чином визначаючи рейтинг учасників. Часто учасники пишуть дуже довгі беззмістовні тексти; наприклад, текст, який складається з 500 000 послідовних 'T', не є рідкістю. І вони ніколи не використовують пропуски.

Ми хочемо швидко визначити, скільки разів слово (тобто певний рядок) зустрічається у тексті. Формалізуємо задачу: мається алфавіт {'A', 'B', 'C', ..., 'Z'} і два скінченних рядки в цьому алфавіті — слово $W$ та текст $T$. Потрібно підрахувати кількість входжень $W$ у $T$. Усі послідовні символи $W$ мають точно відповідати послідовним символам $T$. Входження можуть перекриватися.