Такие задачи обычно легко решаются с помощью подходящего мартингала. Покажем решение на примере строки ОРОР.
Представим казино в котором каждый час происходит розыгрыш подбрасыванием монетки. На N-ом шаге в казино входит человек с одним рублем в кармане и делает ставку в 1 рубль на О. Если выиграл, то на следующем шаге он ставит 2 рубля на Р, если выиграл, то далее ставит 4 рубля на О и так далее постоянно удваивая ставку и ставя на следующую букву нашей последовательности и так до конца нашей последовательности. Если на любом шаге человек проиграл, то он банкрот и выбывает из игры. Каков ожидаемый выигрыш? Если выпадет ОРОР (с вероятностью 1/16) то выигрыш составит 1+2+4+8=15 рублей, во всех остальных 15-ти случаях человек проигрывает 1 рубль, значит ожидаемый выигрыш равен 0 при подобной системе.
Теперь представим, что в казино на каждом шаге входит новый человек и начинает свою игру (которая для него продолжается максимум 4 шага). Совокупный ожидаемый выигрыш всех вошедших очевидно тоже должен быть равен нулю,
а значит является мартингалом.
Теперь как это все используется для вычисления ожидаемого количества шагов N до выпадения ОРОР.
Допустим на N-ом шаге впервые выпало ОРОР. Это значит, что первые N-4 вошедших игроков проиграли по рублю и их совокупный выигрыш равен 4-N. (N-3) -й игрок очевидно выиграл 15 рублей. (N-2)-й проиграл рубль, (N-1)-й выиграл 1+2=3 рубля, и N-й проиграл рубль. То есть совокупный выигрыш всех N игроков равен:
4 - N + 15 -1 + 3 - 1 = 20 - N.
Однако, ожидаемый совокупный выигрыш должен быть равен нулю, значит 20 - N = 0, откуда ожидаемый N = 20.
Этот метод легко обобщается для произвольной строки, и если посмотреть как мы считаем совокупный выигрыш, то понятно что нужно для каждого суффикса, который является префиксом добавить 2^k, где k это длина суффикса.
Интересное рассуждение, я даже новое слово выучил.