Здравствуйте, serjjj, Вы писали:

S>Есть текст, длинной порядка 10^8 — 10^9 букв. Есть некоторая строка длинной порядка 3 букв. Есть гипотеза о том, что эта строка распределена в тексте не случайно, а образует кластеры.

S>Посему есть 2 задачи:
S>1) подтвердить или опровергнуть гипотезу о наличии кластеров,
S>2) найти локализацию всех кластеров данной строки в тексте.

Уточни что у тебя буква ? И порядка 3х букв это 3-4 буквы? Эту строку надо искать один раз или их таких строк целый набор?
И еще кластером ты называешь скопление твоей последовательности скажем >k штук в области <M символов или что-то другое?

Если у тебя алфавит ASCII 8bit на букву. ищем 4 байта подряд. искать надо всего 1 раз и кластер это k раз в отрезке M букв то:
пробигам по всему тексту последовательно и сравниваем *(int32*)data==*(int32*)sample и
паралельно циклично заполняем битовый вектор длинной M аккуратно выставляя 1 если совпало
и 0 если нет. добавляем в статистику этот бит и отнимаем тот что на M шагов был раньше.
Если кол-во бит больше k записывает что гипотиза выполнилась, да и каждое совпадение заносим
в список результатов.
за 1 проход находим то что хотели ( если хотели именно этого )