パターンマッチング手法を使用した文字列長

Question

最初のパターンマッチング手法を使用して長さがTのテキストで長さLの文字列を検索するために必要な比較の最大数はいくらですか？

Answer 1

Knuth–Morris–Pratt algorithmは、O(L+T)という複雑さをもたらします。