m -> Pattern length n -> Text length 1 <= m <=n --------------------------------------------------------------------------------------------------- // NO PREPROCESSING Naive : O((n-m+1)*m) Naive (When all characters of Pattern are distinct) : O(n) --------------------------------------------------------------------------------------------------- // PREPROCESS PATTERN Rabin Karp : O((n-m+1)*m) // But, better then naive on average KMP Algorithm : O(n) --------------------------------------------------------------------------------------------------- // PREPROCESS TEXT Suffix Tree : O(m)