Overview of Pattern Searching in strings

PHOTO EMBED

Tue Feb 08 2022 11:26:01 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #string #patternsearching #overview

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)
content_copyCOPY