Интересная задачка по теме сложности алгоритмов

   В теме "Optimize & Solve Technique #2: DIY (Do It Yourself)" книги Cracking the coding interview Mcdowell есть интересная задачка: 

Given a smaller string S and a bigger string B, design an algorithm to find all permutations of the shorter string within the longer one, print the location of each permutation (даны строки S и B, длина S не больше B, вывести положения всех перестановок строки S в строке B). Пример: S = abbc, B = cbabadcbbabbcbabaabccbabc. 

 
   В процессе решения автор приводит пример алгоритма "в лоб": сформировать все перестановки S и найти их положения в B, сложность O(S! * B). Затем описываются следующие упрощения:

1. Рассматривать B по подстрокам длиной S и проверять каждую такую подстроку в качестве перестановки S;
2. Проверять каждый символ B: если такой символ присутствует в S - проверить подстроку длиной S из B (начиная с этого символа) в качестве перестановки S.

   Данные упрощения позволяют построить алгоритмы сложностью O(B * S log S), O(B * S), O(B * S²) и O(B). К сожалению, в книге приводится только сложность, попробуем восстановить описание алгоритмов по их оценке:

• O(B * S log S) - первое упрощение, где каждая подстрока из B упорядочивается и сравнивается с упорядоченной S;
• O(B * S) - второе упрощение с посимвольной проверкой (два цикла: один по B и вложенный по S);
• O(B) - сформируем некоторый шаблон f(S) для строки S, последовательно проходя цикл из B сформируем шаблон текущей подстроки длиной S и сравним с f(S). Важное отличие от предыдущего варианта - нет вложенного цикла по S. Сам шаблон не должен учитывать позиции символов (для поиска перестановок). Для рассматриваемого примера: длина S = 4, зададим для каждого символа "алфавита" некоторое значение а=100, b=1, c=10, d=1000, шаблон - сумма значений, то есть f(S) = 100+1+1+10=112 (данное значение сохраняем). Берем первую подстроку из B длиной 4 символа ("cbab"), запоминаем значение первого символа в переменную Z (в данном случае это 10), считаем значение для текущей подстроки (10+1+100+1 = 112) и сравниваем с f(S), если значение совпадает - значит нашлась перестановка (в данном случае так и есть). Затем берем следующий символ из B (пятый символ - "a"), сохраняем его значение (100) в переменную Y. Из значения для предыдущей подстроки вычитаем Z, прибавляем Y (112 - 10 + 100 = 202), сравниваем c f(S) и т.д.

   Из описанных сложностей так и не смог придумать алгоритм для O(B * S²) - если есть идеи - просьба поделиться :) Можно, конечно, использовать более долгий вариант сортировки, но автор скорее всего имел ввиду другую идею.