Preview:
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)
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