Search a long string for small strings in an array

 Posted on July 23, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given a string s and an array of smaller strings T, design a method to search s for each small string in T. Solution Method 1 - Using suffix tree We can first get all the suffices of s and check for each element t in T to see if t is the beginning part of any suffices. To make this more efficient, we can build a suffix tree and do the operations. [Read More]
StringAlgo  kodeknight  suffix tree  hard  pattern matching  CrackingTheCodingInterview 

String Searching Algorithm - Knuth Morris Pratt or KMP Algorithm

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Knuth-Morris-Pratt string searching algorithm: - This algorithm searches a word->w within the main string text->s - Such a search must employ the following observation: i) A given match determines where the next match could begin ii) The above intelligence is obtained for the search word itself that contains sufficient information for making such a discussion (i.e. determine where the next match begins) Advantage of this string searching algorithm: Helps to avoid the re-examination of already matched characters [Read More]
Algorithms  kodeknight  String  string-search  search string  incomplete  match string  Data Structure  pattern matching  KMP algorithm