# C Program to Implement KMP Pattern Searching Algorithm

«
»

The KMP algorithm is a very fast algorithm for string matching. It is used in many applications like searching for a substring in a large string. The algorithm is based on the idea that if we know the longest prefix of the pattern that is also a suffix of the pattern, then the pattern can be searched in O(n) time. This is called the Knuth-Morris-Pratt algorithm. If a mismatch occurs, we can simply skip the characters of the pattern already matched. We can do this by specifying the length of the longest prefix which is also a suffix. This way we can skip the characters of the pattern already matched. This is called the skip table.

Pattern searching is used for finding the existence of a substring in a string. The pattern searching in the following has been made case-insensitive.

Knuth Morris Pratt Algorithm:

1. Take the word as input.
2. Take the main string as input.
3. Create a skip table for the word.
4. Create a variable to store the index of the word.
5. Create a variable to store the index of the main string.
6. Loop through the main string and check whether the word is a substring of the main string.
7. If the word is a substring of the main string, print the index of the word.
8. If the word is not a substring of the main string, print the index of the main string.
9. Repeat the process until the end of the main string is reached.

Problem description

Write a C program that will ask the user for a word and a main string and then search for the occurrences for the word in the main string.

Problem Solution

In this naive approach, we’ll not make use of any functions. We’ll just loop through all the characters of the main string and check whether the word is a substring of the main string.

Example 1:

Note: Join free Sanfoundry classes at Telegram or Youtube

Input:

word: abc
main string: abcdefabc

Output:
The word is found at index 0
The word is found at index 6

Example 2:

Take C Programming Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Input:

word: aba
main string: abc ana dhg aana aba

Output:
The word is found at index 17

Program/Source Code

Here is a source code of the C program that implement KMP Pattern Searching algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `/*`
2. ` * C Program to Implement the KMP Pattern Searching Algorithm  `
3. ` */`
4. ` `
5. `#include <stdio.h>`
6. `#include <string.h>`
7. `#include <ctype.h>`
8. ` `
9. `void inputLine(char *line, int maxLen)`
10. `{`
11. `    fflush(stdin);`
12. `    int i = 0;`
13. `    char c;`
14. `    while ((c = getchar()) != '\n' && i < maxLen)`
15. `    {`
16. `        line[i++] = tolower(c);`
17. `    }`
18. `    line[i] = '\0';`
19. `}`
20. ` `
21. `int main(void)`
22. `{`
23. `    char word;`
24. `    char mainString;`
25. `    int i, j, k;`
26. `    int wordLen, mainStringLen;`
27. `    int skipTable;`
28. `    int wordIndex, mainStringIndex;`
29. `    printf("Enter the word: ");`
30. `    inputLine(word, 100);`
31. `    printf("Enter the main string: ");`
32. `    inputLine(mainString, 100);`
33. `    wordLen = strlen(word);`
34. `    mainStringLen = strlen(mainString);`
35. `    for (i = 0; i < wordLen; i++)`
36. `    {`
37. `        skipTable[i] = 1;`
38. `    }`
39. `    for (i = 1; i < wordLen; i++)`
40. `    {`
41. `        j = i - 1;`
42. `        k = i;`
43. `        while (j >= 0 && word[j] == word[k])`
44. `        {`
45. `            skipTable[k] = j + 1;`
46. `            j--;`
47. `            k--;`
48. `        }`
49. `    }`
50. `    wordIndex = 0;`
51. `    mainStringIndex = 0;`
52. `    while (mainStringIndex < mainStringLen)`
53. `    {`
54. `        if (word[wordIndex] == mainString[mainStringIndex])`
55. `        {`
56. `            wordIndex++;`
57. `            mainStringIndex++;`
58. `        }`
59. `        else`
60. `        {`
61. `            mainStringIndex += skipTable[wordIndex];`
62. `            wordIndex = 0;`
63. `        }`
64. `        if (wordIndex == wordLen)`
65. `        {`
66. `            printf("The word is found at index %d\n", mainStringIndex - wordLen);`
67. `            wordIndex = 0;`
68. `        }`
69. `    }`
70. `    if (wordIndex != 0)`
71. `    {`
72. `        printf("The word is not found\n");`
73. `    }`
74. `    return 0;`
75. `}`
Program Explanation

1. Take the word as input and store the word in a variable.
2. Take the main string as input and store the main string in a variable.
3. Create a skip table for the word and also create a variables to store the index of the word and main string.
4. In this approach, we’ll loop through all the characters of the main string and check whether the word is a substring of the main string.
5. If the word is a substring of the main string, we’ll print the index of the word.
6. If the word is not a substring of the main string, we’ll print the index of the main string.
7. Repeat the process until the end of the main string is reached.

Time complexity: O(n)
Time complexity of this algorithm is O(n), where n is the number of elements in the string.

Space Complexity: O(n)
Space is required to store the string, so the space complexity of this algorithm is O(n).

Runtime Test Cases

Testcase 1: In this case, we enter the word as “aba” and the main string is “abc ana dhg aana aba” as input.

```Enter the word: aba
Enter the main string: abc ana dhg aana aba

The word is found at index 17```

Testcase 2: In this case, we enter the word as “abc” and the main string is “abcdefabc” as input.

```Enter the word: abc
Enter the main string: abcdefabc

The word is found at index 0
The word is found at index 6```

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”. 