KMP algorithm

Problem  The program has to detect all occurences of the needle in the haystack. It should take the needle and the haystack as input, and output the positions of each occurence, as shown below. Input The input consists of a number of test cases. Each test case is composed of three lines, containing: the length of the needle, the needle itself, the haystack. Output For each test case your program should output all positions of the needle’s occurences within the haystack. [Read More]

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]