Z algorithm を用いると、各 \(1 \leq i \leq |T|\) について「 \(T\) の \(i\) 文字目以降と \(S\) の Longest Common Prefix」を求めることができます。この値を \(m_i\) とおきます。

以下のようなグラフにおける頂点 \(1\) から頂点 \(|T| + 1\) への最短経路が答えとなります。

• 頂点は \(1, \dots, |T| + 1\) の \(|T|+1\) 個
• 各 \(1 \leq i \leq |T|\) について、頂点 \(i+1\) から頂点 \(i\) へ向かう重み \(0\) の辺が存在する。
• 各 \(1 \leq i \leq |T|\) について、頂点 \(i\) から頂点 \(i + m_i\) ヘ向かう重み \(1\) の辺が存在する。

これは 01-BFS と呼ばれる手法を用いて \(O(|T|)\) で計算できます。
全体の計算量は \(O(|S| + |T|)\) となります。

実装例 (C++)