string-search

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]

Some points to note about this String matching algorithm: uses an hashing function; preprocessing phase in O(m) time complexity and constant space; searching phase in O(m__n) time complexity; O(n_+_m) expected running time. Instead of checking at each position of the text if the pattern occurs or not, it is better to check first if the contents of the current string “window” looks like the pattern or not. In order to check the resemblance between these two patterns, a hashing function is used. [Read More]

Pattern matching program using Brute Force Algorithm(Source Code) // Program Example Ch03pr05 // Pattern matching program using Brute Force Algorithm #include #include #include const int MAX = 20 ; class string { private :  char str[MAX] ;  public :  string( ) ; string ( char *s ) ; static int xstrsearch ( string &s1, string &s2 ) ; void show( ) ; } ; // initializes data [Read More]