C program to implement Knuth–Morris–Pratt algorithm

Write a C program to implement Knuth–Morris–Pratt algorithm.

• Knuth-Morris-Pratt(KMP) is a string matching algorithm.
• It helps to find the search string in the given target string with minimal comparisons.
• For the target string of length n and patter string of length m, the running time of the KMP algorithm is O(m+n).
• KMP algorithm involves two phases.  They are finding the overlap in the pattern and finding pattern in target string.

How to find the overlap in the given pattern?

Here, we need to find suffix(in the pattern) that matches prefix of the given pattern.  For example, "abcdabd" is the input string.  "ab" at the end is the suffix that matches the prefix "ab" at the start  => abcdabd

Algorithm to find overlap in the given pattern:

Input   :  pattern in which overlap needs to be found

Output:  Overlap array

        i<-2, j<-0, len<-strlen(pattern)

        overlap[0] <- -1, overlap[1] <-  0

        while  i < len 

                if  pattern[i - 1] equal to pattern[j]

                        j <- j + 1, ptr[i++] <- j;

                otherwise if j greater than 0

                        j <- ptr[j]

                otherwise

                        ptr[i++] <- 0

        end while

i = 2, j = 0
Pattern :   a | b | c | d | a | b | d |
Overlap :  -1 | 0 | 0 |

i = 3, j = 0
Pattern :  a | b | c | d | a | b | d |
Overlap : -1 | 0 | 0 | 0 |

i = 4, j = 0
Pattern :  a | b | c | d | a | b | d |
Overlap : -1 | 0 | 0 | 0 | 0 |

i = 5, j = 0
Pattern :  a | b | c | d | a | b | d |
Overlap : -1 | 0 | 0 | 0 | 0 | 1 |

i = 6, j = 1
Pattern :  a | b | c | d | a | b | d |
Overlap : -1 | 0 | 0 | 0 | 0 | 1 | 2 |

Algorithm for Knuth-Morris-Pratt(KMP) Searching:

Input    : Target string, Pattern and Overlap array

Output :  Index of the Pattern in Target string

        i->0, j->0, count->0

        while i + j is lesser than  strlen(Target)

                if pattern[j] equals Target[i + j],

                        if j equals strlen(word) - 1)

                                return index of pattern

                        j <- j + 1;

                otherwise,

                        i <- i + j - overlap[j];

                        if overlap[j] is greater than -1)

                                j <- overlap[j]

                        otherwise,

                                j <- 0;

         end while

Target : abc abcdabcdabd

Pattern: abcdabd

i => 0 , j=> 0
Target[i + j] and Pattern[j] are same.  So, increment j.

Target :  abc abcdabcdabd

Pattern:  abcdabd

i => 0, j=> 1
Target[i + j] and Pattern[j] are same.  So, increment j.

Target :  abc abcdabcdabd

Pattern:  abcdabd

i => 0 , j=> 2
Target[i + j] and Pattern[j] are same.  So, increment j.

Target :  abc abcdabcdabd

Pattern:  abcdabd

i => 0 , j=> 3
Target[i + j] and Pattern[j] are not same.

Target : abc abcdabcdabd

Pattern: abcdabd

i <- i + j - overlap[3] => 0 + 3 - 0 => 3

j <- overlap[j] => overlap[3] => 0

i => 3 , j=> 0
Target[i + j] and Pattern[j] are not same.

Target :  abc abcdabcdabd

Pattern:       abcdabd

i <- i + j - overlap[0] => 3 + 0 - (-1) => 4

j <- 0

i => 4 , j=> 0
Target[i + j] and Pattern[j] are same.  So, increment j.

Target : abc abcdabcdabd

Pattern:       abcdabd

i => 4 , j=> 1
Target[i + j] and Pattern[j] are same.  So, increment j.

Target : abc abcdabcdabd

Pattern:       abcdabd

i => 4 , j=> 2
Target[i + j] and Pattern[j] are same.  So, increment j.

Target : abc abcdabcdabd

Pattern:       abcdabd

i => 4 , j=> 3
Target[i + j] and Pattern[j] are same.  So, increment j.

Target : abc abcdabcdabd

Pattern:       abcdabd

i => 4 , j=> 4
Target[i + j] and Pattern[j] are same.  So, increment j.

Target : abc abcdabcdabd

Pattern:       abcdabd

i => 4 , j=> 5
Target[i + j] and Pattern[j] are same.  So, increment j.

Target : abc abcdabcdabd

Pattern:       abcdabd

i => 4 , j=> 6
Target[i + j] and Pattern[j] are not same.

Target : abc abcdabcdabd

Pattern:       abcdabd

i <- i + j - overlap[6] => 4 + 6 - 2 => 8

j <- overlap[j] => overlap[6] => 2

i => 8 , j=> 2
Target[i + j] and Pattern[j] are same.  So, increment j.

Target : abc abcdabcdabd

Pattern:              abcdabd

i => 8 , j=> 3
Target[i + j] and Pattern[j] are same.  So, increment j.

Target : abc abcdabcdabd

Pattern:             abcdabd

i => 8 , j=> 4
Target[i + j] and Pattern[j] are same.  So, increment j.

Target : abc abcdabcdabd

Pattern:              abcdabd

i => 8 , j=> 5
Target[i + j] and Pattern[j] are same.  So, increment j.

Target : abc abcdabcdabd

Pattern:              abcdabd

i => 8 , j=> 6

Target : abc abcdabcdabd

Pattern:              abcdabd

Finally, match Found!!!

C program to implement Knuth–Morris–Pratt algorithm(KMP String Matching):

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

  /* 
   * finds the position of the pattern in the given target string
   * target - str, patter - word
   */

  int  kmpSearch(char *str, char *word, int *ptr) {
        int i = 0, j = 0;

        while ((i + j) < strlen(str)) {
                /* match found on the target and pattern string char */
                if (word[j] == str[i + j]) {
                        if (j == (strlen(word) - 1)) {
                                printf("%s located at the index %d\n",
                                        word, i + 1);
                                return;
                        }
                        j = j + 1;
                } else {
                        /* manipulating next indices to compare */
                        i = i + j - ptr[j];
                        if (ptr[j] > -1) {
                                j = ptr[j];
                        } else {
                                j = 0;
                        }
                }
        }
  }

  /* find the overlap array for the given pattern */

  void findOverlap(char *word, int *ptr) {

        int i = 2, j = 0, len = strlen(word);

        ptr[0] = -1;

        ptr[1] = 0;

        while (i < len) {

                if (word[i - 1] == word[j]) {

                        j = j + 1;

                        ptr[i] = j;

                        i = i + 1;

                } else if (j > 0) {

                        j = ptr[j];

                } else {

                        ptr[i] = 0;

                        i = i + 1;

                }

        }

        return;

  }

  int main() {

        char word[256], str[1024];;

        int *ptr, i;

        /* get the target string from the user */

        printf("Enter your target string:");

        fgets(str, 1024, stdin);

        str[strlen(str) - 1] = '\0';

        /* get the pattern string from the user */

        printf("Enter your pattern string:");

        fgets(word, 256, stdin);

        word[strlen(word) - 1] = '\0';

        /* dynamic memory allocation for overlap array */

        ptr = (int *)calloc(1, sizeof(int) * (strlen(word)));

        /* finds overlap array */

        findOverlap(word, ptr);

        /* find the index of the pattern in target string */

        kmpSearch(str, word, ptr);

        return 0;

  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your target string: abc abcdabcdabd
  Enter your pattern string: abcdabd
  abcdabd located at the index 9

C program to print all interleaving of two strings

An interleaving can be formed using the characters present in the given two input strings.  But, the order of characters in each string needs to be maintained.

For example, str1 = "12" and str2 = "34".  Then the possible interleavings are as follows.
1234
1324
1342
3124
3142
3412

The length of each interleaving is equal to the sum of length of the given two input strings.  And the number of possible interleavings can be found using the below formula.

(m+n)Cm =  (m+n)! / m!((m + n) - m) !

Write a C program to print all interleaving of two strings.

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

  /* prints all possible interleavings of given two input strings */
  void interleave(char *str1, char *str2, char * output, int len) {
        if (*str1 == '\0' && *str1 == '\0') {
                /* prints the interleaving */
                if (*(output - len))
                        printf("%s\n", output - len);
        }

        /* interleaving manipulation */
        if (*str1 != '\0') {
                output[0] = str1[0];
                interleave(str1 + 1, str2, output + 1, len);
        }

        if (*str2 != '\0') {
                output[0] = str2[0];
                interleave(str1, str2 + 1, output + 1, len);
        }

        return;
  }

  int main() {

        int len;

        char str1[256], str2[256], output[512];

        /* get the first input string from the user */

        printf("Enter your first input string:");

        fgets(str1, 256, stdin);

        str1[strlen(str1) - 1] = '\0';

        /* get the second input string from the user */

        printf("Enter your second input string:");

        fgets(str2, 256, stdin);

        str2[strlen(str2) - 1] = '\0';

        /* length of each interleaving */

        len = strlen(str1) + strlen(str2);

        /* initializing output array */

        memset(output, '\0', sizeof(output));

        /* prints all possible interleavings */

        interleave(str1, str2, output, len);

        return 0;

  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your first input string:12
  Enter your second input string:34
  1234
  1324
  1342
  3124
  3142
  3412

C program to print the frequency of words in a string

Write a C program to count the frequency of words in a string.

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

  int main() {
        char string[256], text[256], words[100][256], temp[256];
        int i, j, k, n, count;

        i = j = k = n = 0;

        /* get the input string from the user */
        printf("Enter your input string:");
        fgets(string, 256, stdin);
        string[strlen(string) - 1] = '\0';

        /* copying each and every word from the string */
        while (string[i] != '\0') {
                if (string[i] == ' ') {
                        words[j][k] = '\0';
                        k = 0;
                        j++;
                } else {
                        words[j][k++] = string[i];
                }
                i++;
        }

        words[j][k] = '\0';
        n = j;

        /* sort the words in the given string */

        for (i = 0; i < n; i++) {

                strcpy(temp, words[i]);

                for (j = i + 1; j <= n; j++) {

                        if (strcmp(words[i], words[j]) > 0) {

                                strcpy(temp, words[j]);

                                strcpy(words[j], words[i]);

                                strcpy(words[i], temp);

                        }

                }

        }

        printf("Frequency of words:\n");

        i = 0;

        /* find the frequency of each word and print the results */

        while (i <= n) {

                count = 1;

                if (i != n) {

                        for (j = i + 1; j <= n; j++) {

                                if (strcmp(words[i], words[j]) == 0) {

                                        count++;

                                }

                        }

                }

                /* count - indicates the frequecy of word[i] */

                printf("%s\t%d\n", words[i], count);

                /* skipping to the next word to process */

                i = i + count;

        }

        printf("\n");

        return 0;

  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your input string:apple bat apple ball bat ball cat rat cat ball
  Frequency of words:
  apple     2
  ball        3
  bat        2
  cat        2
  rat        1

C program to remove duplicate words in a string

Write a C program to print unique words in a string.

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

  int main() {
        char string[256], text[256], words[100][256];
        int i, j, k, n;

        i = j = k = n = 0;

        /* get the input string from the user */
        printf("Enter your input string:");
        fgets(string, 256, stdin);
        string[strlen(string) - 1] = '\0';

        /* copying each and every word from the string */
        while (string[i] != '\0') {
                if (string[i] == ' ') {
                        words[j][k] = '\0';
                        k = 0;
                        j++;
                } else {
                        words[j][k++] = string[i];
                }
                i++;
        }

        words[j][k] = '\0';
        n = j;

        /* remove duplicate words in the given string */

        for (i = 0; i < n; i++) {

                for (j = i + 1; j <= n; j++) {

                        if (strcmp(words[i], words[j]) == 0) {

                                for (k = j; k < n; k++) {

                                        strcpy(words[k], words[k + 1]);

                                }

                                n--, j--;

                        }

                }

        }

        /* print the unique words */

        for (i = 0; i <= n; i++) {

                printf("%s ", words[i]);

        }

        printf("\n");

        return 0;

  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your input string:hello world hello world hello hello hell
  hello world hell 

C program to remove the occurrence of the word from entered string

Write a C program to remove all occurrence of the word from entered string.

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

  int main() {
        char string[256], text[256], words[100][256];
        int i, j, k, n, flag;

        i = j = k = 0;;

        /* get the input string from the user */
        printf("Enter your input string:");
        fgets(string, 256, stdin);
        string[strlen(string) - 1] = '\0';

        /* get the word that needs to be removed from i/p string */
        printf("Enter the word your want to remove:");
        fgets(text, 256, stdin);
        text[strlen(text) - 1] = '\0';

        /* copying each and every word from the string */
        while (string[i] != '\0') {
                if (string[i] == ' ') {
                        words[j][k] = '\0';
                        k = 0;
                        j++;
                } else {
                        words[j][k++] = string[i];
                }
                i++;
        }

        words[j][k] = '\0';

        /* print all words except the word that needs to be removed */

        for (i = 0; i <= j; i++) {

                if (strcmp(words[i], text) != 0) {

                        printf("%s ", words[i]);

                }

        }

        printf("\n");

        return 0;

  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your input string:Hai Hello.. How are you?
  Enter the word your want to remove:Hai
  Hello.. How are you? 

C program to insert a word in a string

Write a C program to insert a word into the string at the given location.

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

  int main() {
        char string[256], word[256], output[512];
        int i, j, k, location;

        i = j = k = 0;

        /* get the input string from the user */
        printf("Enter your input string:");
        fgets(string, 256, stdin);
        string[strlen(string) - 1] = '\0';

        /* get the input word from the user  */
        printf("Enter the word to insert:");
        fgets(word, 32, stdin);
        word[strlen(word) - 1] = '\0';

        /* get the desired location to insert input word */
        printf("Enter your desired location(0-%d):", strlen(string) - 1);
        scanf("%d", &location);

        /* copying characters present before the given location */
        for (i = 0; i < location; i++) {
                output[j++] = string[i];
        }

        /* copying the given word */
        while (word[k] != '\0') {
                output[j++] = word[k++];
        }

        /* copying characters present after the given location */

        while (string[i] != '\0') {

                output[j++] = string[i++];

        }

        output[j] = '\0';

        /* print the result */

        printf("Resultant String: %s\n", output);

        return 0;

  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out 
  Enter your input string:helloworld
  Enter the word to insert:       //given space as i/p
  Enter your desired location(0-9):5 
  Resultant String: hello world

C program to print the ascii value of all characters in a string

Write a C program to print the ASCII value of all characters in a string.

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

  int main() {
        char string[256];
        int i = 0;

        /* get the input string from the user */
        printf("Enter your input string:");
        fgets(string, 256, stdin);
        string[strlen(string) - 1] = '\0';

        /* prints ascii value of all characters in the i/p string */
        while (string[i] != '\0') {
                printf("Character: %c\tASCII: %d\n",
                                        string[i], string[i]);
                i++;
        }

        return 0;
  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your input string:HelloWorld
  Character: H ASCII: 72
  Character: e ASCII: 101
  Character: l ASCII: 108
  Character: l ASCII: 108
  Character: o ASCII: 111
  Character: W ASCII: 87
  Character: o ASCII: 111
  Character: r ASCII: 114
  Character: l ASCII: 108
  Character: d ASCII: 100

C program to wrap a text

Write a C program to wrap a text.

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

  int main() {
        char ptr[256];
        int i, n;

        /* get the input string from the user */
        printf("Enter your input string:");
        fgets(ptr, 256, stdin);
        ptr[strlen(ptr) - 1] = '\0';

        /* get the input to wrap the text */
        printf("I/P to wrap the given string(0 to %d):", strlen(ptr) - 1);
        scanf("%d", &n);

        /* boundary check */
        if (n < 0 || n > strlen(ptr) - 1) {
                printf("Boundary Value Exceeded!!\n");
                return 0;
        }

        /* wrapping the string to n characters */
        ptr[n] = '\0';

        /* print the result */
        printf("After Wrapping the given Text to %d characters..\n", n);
        printf("Resultant String: %s\n", ptr);

        return 0;
  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your input string:Hello world
  I/P to wrap the given string(0 to 10):5
  After Wrapping the given Text to 5 characters..
  Resultant String: Hello

C program to trim a string

Write a C program to trim a string.

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

  int main() {
        char str[256];
        int start, end, i;

        /* get the input string from the user */
        printf("Enter your input string:");
        fgets(str, 256, stdin);
        str[strlen(str) - 1] = '\0';

        /* get the portion to trim */
        printf("Start & End Point to trim(0-%d):\n", strlen(str) - 1);
        scanf("%d%d", &start, &end);

        /* boundary check */
        if (start > end || start < 0 || end > strlen(str) - 1) {
                printf("Boundary Value Exceeded!!\n");
                return 0;
        }

        /* Trim the given range of characters and print remaining string */
        printf("Resultant String:\n");
        for (i = 0; i < start; i++) {
                printf("%c", str[i]);
        }

        for (i = end + 1; i < strlen(str); i++) {
                printf("%c", str[i]);
        }

        printf("\n");
        return 0;
  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your input string:hello world
  Start & End Point to trim(0-10):
  0 5
  Resultant String:
  world

C program to rotate a string

Write a C program to rotate the given string.

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

  /* prints characters from str[n] to end of string */
  void printChar(char *str, int n) {
        int i;
        for (i = n; i < strlen(str); i++) {
                printf("%c", *(str + i));
        }
        return;
  }

  /* prints first n characters in the given string */
  void printRev(char *str, int n) {
        int i = 0;
        while (i <= n) {
                printf("%c", *(str + i));
                i++;
        }
        return;
  }

  int main() {

        char rotate[256];

        int i;

        /* get the input string from the user */

        printf("Enter input string to rotate:");

        fgets(rotate, 256, stdin);

        rotate[strlen(rotate) - 1] = '\0';

        printf("Rotating Input String:\n");

        /* if the given string has >= 1 character */

        if (strlen(rotate) <= 1) {

                printf("%s\n", rotate);

                return 0;

        }

        printf("%s\n", rotate);

        /* rotate the given string */

        for (i = 1; i < strlen(rotate); i++) {

                /* prints characters from rotate[i] to end */

                printChar(rotate, i);

                /* prints characters from rotate[0]  to rotate[i-1] */

                printRev(rotate, i - 1);

                printf("\n");

        }

        return 0;

  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter input string to rotate:india
  Rotating Input String:
  india
  ndiai
  diain
  iaind
  aindi

C program to generate all possible substring of a string

Write a C program to print all possible substrings of a given string.

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

  /* prints num character from the character array ptr */
  void printchar(char *ptr, int num) {
        int i;
        for (i = 0; i < num; i++) {
                printf("%c", *(ptr + i));
        }
        printf("\n");
        return;
  }


  int main() {
        char str[256];
        int i = 0, j;

        /* get the input string from the user */
        printf("Enter your input string:");
        fgets(str, 256, stdin);
        str[strlen(str) - 1] = '\0';

        /* find and print the possible substrings */
        printf("\nPossible Substrings:\n");
        while (str[i] != '\0') {
                /* printing possible substrings */
                for (j = 1; j <= strlen(str) - i; j++) {
                        /* prints j characters from str[i] */
                        printchar((str + i), j);
                }
                i++;
        }
        return 0;
  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your input string:India  
  Possible Substrings:
  I
  In
  Ind
  Indi
  India
  n
  nd
  ndi
  ndia
  d
  di
  dia
  i
  ia
  a

C program to find the number of words starting with vowel

Write a C program to print the words starting with vowel.

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

  /* checks whether the given character is vowel */
  int isVowel(char ch) {
        int i;
        char vowels[] = {'a', 'e', 'i', 'o', 'u',
                         'A', 'E', 'I', 'O', 'U'};

        for (i = 0; i < 10; i++) {
                if (ch == vowels[i]) {
                        return 1;
                }
        }

        return 0;
  }

  int main() {
        char myStr[256], word[256];
        int i = 0, j = 0, ch, count = 0;

        /* get the input string from the user */
        printf("Enter your input string:");
        fgets(myStr, 256, stdin);
        myStr[strlen(myStr) - 1] = '\0';

        printf("Words Starting With Vowel:\n");

        /*
         * copying word by word and prints words
         * starting with vowels.
         */

        while (myStr[i] != 0) {

                if(myStr[i] == ' ') {

                        word[j] = '\0';

                        j = 0;

                        /*

                         * checks whether the word starts

                         * with vowel

                         */

                        if (isVowel(word[j])) {

                                printf("%s\n", word);

                                count++;

                        }

                        i++;

                        continue;

                }

                word[j++] = myStr[i];

                i++;

        }

        word[j] = '\0';

        /* print if the last word in the string is vowel */

        if (isVowel(word[0])) {

                printf("%s\n", word);

                count++;

        }

        /* prints the number of words starting with vowel */

        printf("Number of word starting with vowels: %d\n", count);

        return 0;

  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your input string:A old man lived alone in india
  Words Starting With Vowel:
  A
  old
  alone
  in
  india
  Number of word starting with vowels: 5