例えば，\(s\) が abcde の繰り返しであるケースをまず考えます． これは簡単に解くことができます． \(t\) の \(i\) 文字目が，\(s\) の中で登場する位置を \(f_i\) と書くことにします．ところで，\(f_i \bmod 5\) の値は \(t_i\) の文字によって定まっているので，\(g_i=floor((f_i+4)/5)\) とおいて \(g_i\) だけを考えることにします．

\(t_i,t_{i+1}\) の文字に応じて，\(g_i \leq g_{i+1}\) または \(g_i < g_{i+1}\) という制約が発生します．また，当然ですが，\(1\leq g_i \leq N\) です． ここで，今上げた制約を満たす列 \(g_i\) の数が，\(s\) から \(t\) を取り出す方法の数になっています． この値は簡単なコンビネーションの式で求められます．

\(s\) が keyence であるケースに戻りましょう． 上で説明した方法は，e の文字を \(\bmod 7\) でどこに対応させるかが定まらないため，そのまま適用することはできません．（逆に e 以外については定まることに注意してください．）

そこで，\(t_i\) のそれぞれの e について，\(\bmod 7\) での位置を固定したとします． すると，\(g_i \leq g_{i+1}\) または \(g_i < g_{i+1}\) という制約が出てきて，条件を満たす列 \(g_i\) の個数を数える問題になります． 先程この個数はコンビネーションの式で求められると言いましたが，この式は，\(g_i < g_{i+1}\) という制約になっている \(i\) の個数のみに依存する形でかけます．(他の変数は \(N\),\(|t|\) など入力から定まる値のみです．）

\(g_i\) と \(g_{i+1}\) の制約が入力から定まらないのは，e が関係する部分です． 入力の文字列の e が連続する極大な部分について，以下の問題が解ければよいです．

• e の \(\bmod 7\) での位置は各文字あたり \(3\) 通りあるが，\(g_i <g_{i+1}\) という制約の個数が \(k\) になる割り当て方は何通りあるか？

今見ている e の列の長さを \(L\) とします． この問題は，FFT と繰り返し二乗法を用いると \(O(L\log L)\) で解くことができます．ただし，先頭と末尾の e の \(\bmod 7\) の値で分類する必要があり，計算には \(27\) 倍の定数がかかります． （Quiz: 値の候補が \(k\) 通りの時，今のアルゴリズムでは \(O(k^3 L \log L)\) ですが，\(O(kL+L\log L)\) で解く方法も存在します．）

最後に，各極大部分列に対する答えを多項式と見て，すべて乗算すればよいです．これは \(O(|T| \log^2 |T|)\) 時間で行なえます．

よって，全体で \(O(|T| \log^2 |T|)\) 時間でこの問題は解けます．