Home » C programs » C string programs

C program to implement the KMP pattern search algorithm

Here, we are going to learn how to implement the KMP pattern search algorithm in C programming language?
Submitted by Nidhi, on July 23, 2021

Problem statement

Read a string from the user, then find the word in the string using the KMP pattern search algorithm, and print the index of the word within string on the console screen.

C program to implement the KMP pattern search algorithm

The source code to implement the KMP pattern search algorithm is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.

// C program to implement the KMP pattern search algorithm

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main()
{
    char str[64];
    char word[20] = "is";

    int i = 0;
    int j = 0;
    int c = 0;

    int index = 0;
    int length = 0;

    printf("Enter string: ");
    scanf("%[^\n]s", str);

    while (str[i]) {
        str[i] = tolower(str[i]);
        i++;
    }

    length = strlen(str) - strlen(word) + 1;
    for (i = 0; i < length; i++) {
        index = i;
        if (str[i] == word[j]) {
            do {
                i++;
                j++;

            } while (j != strlen(word) && str[i] == word[j]);

            if (j == strlen(word)) {
                printf("Word '%s' found from index %d to %d.\n", word, index + 1, i);
                return 0;
            }
            else {
                i = index + 1;
                j = 0;
            }
        }
    }

    printf("No word found in the string.\n");

    return 0;
}

Output

Enter string: This is india
Word 'is' found from index 3 to 4.

Explanation

In the main() function, we read a string from the user and search a specific word within the string using the KMP search algorithm and printed the index of matched word in the string on the console screen.

C String Programs »