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.
10. If the word is not found, print “The word is not found”.

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:

advertisement
advertisement

Input:

word: abc
main string: abcdefabc

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

Example 2:

Note: Join free Sanfoundry classes at Telegram or Youtube

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[100];
  24.     char mainString[100];
  25.     int i, j, k;
  26.     int wordLen, mainStringLen;
  27.     int skipTable[100];
  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.
8. If the word is not found, print “The word is not found”.

advertisement

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.

advertisement
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”.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.