fork download
copy 
  1.  
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. void KMP(char *text, char *pat) {
  6.     int n = strlen(text);
  7.     int m = strlen(pat);
  8.  
  9.     // build LPS array
  10.     int lps[m];
  11.  
  12.     int len = 0;
  13.     lps[0] = 0;
  14.  
  15.     int i = 1;
  16.     while (i < m) {
  17.         if (pat[i] == pat[len]) {
  18.             len++;
  19.             lps[i] = len;
  20.             i++;
  21.         } else {
  22.             if (len != 0) {
  23.                 len = lps[len - 1];
  24.             } else {
  25.                 lps[i] = 0;
  26.                 i++;
  27.             }
  28.         }
  29.     }
  30.  
  31.     // search phase
  32.     i = 0;      // text index
  33.     int j = 0;  // pattern index
  34.  
  35.     int found = 0;
  36.  
  37.     while (i < n) {
  38.         if (text[i] == pat[j]) {
  39.             i++;
  40.             j++;
  41.         }
  42.  
  43.         if (j == m) {
  44.             printf("Pattern found at index %d\n", i - j);
  45.             found = 1;
  46.             j = lps[j - 1];
  47.         }
  48.         else if (i < n && text[i] != pat[j]) {
  49.             if (j != 0)
  50.                 j = lps[j - 1];
  51.             else
  52.                 i++;
  53.         }
  54.     }
  55.  
  56.     if (!found) {
  57.         printf("No match found\n");
  58.     }
  59. }
  60.  
  61. int main() {
  62.     char text[] = "bcd egfpqr";
  63.     char pat[]  = "efg";
  64.  
  65.     KMP(text, pat);
  66.  
  67.     return 0;
  68. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
No match found
https://ideone.com/wuvMeo
language:
C (gcc 8.3)
created:
12 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!