Knuth–Morris–Pratt Algorithm

Introduction

In computer science, The Knuth–Morris–Pratt Algorithm is an string searching algorithm. String Searching Algorithm means the algorithm that searches for the occurrence of a Word(W) in a main Text String(S). This algorithm tries to find the starting index m in string S[] that matches the search word W[].

To illustrate the details of algorithm, consider a run of the algorithm, where W = "abbc" and S = "abxabyabbc".

i : 0123456789
S : abxabyabbc
W : abbc