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)
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter