String Searching Algorithm - Knuth Morris Pratt or KMP Algorithm

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

Step1:

returns: No match found!
Search algorithms observation: We notice no string->'s'(i.e. word position->i[0]) occurs between position w[0] & w[8] in the main string text except at w[5]. Hence, the next character matching operation begins at w[5].

Step2:

returns: Match found!
Search algorithms observation: We notice all strings of the word occurs between position w[5] & w[3] in the main string text. The next character matching operation begins at w[4].

Step 3:

returns: No match found!
Search algorithms observation: We notice no string->'s'(i.e. word position->i[0]) occurs between position w[4] & w[9] in the main string text. The character matching operation ends here.

http://dev-faqs.blogspot.in/2010/05/knuth-morris-pratt-algorithm.html
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/