fork download
copy 
  1.  
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. int KMP(char *text, char *pat) {
  6.     int n = strlen(text);
  7.     int m = strlen(pat);
  8.  
  9.     // build LPS inside KMP
  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.     while (i < n) {
  36.         if (text[i] == pat[j]) {
  37.             i++;
  38.             j++;
  39.         }
  40.  
  41.         if (j == m) {
  42.             return 1; // found
  43.         }
  44.         else if (i < n && text[i] != pat[j]) {
  45.             if (j != 0)
  46.                 j = lps[j - 1];
  47.             else
  48.                 i++;
  49.         }
  50.     }
  51.  
  52.     return 0;
  53. }
  54.  
  55. int main ()
  56. { 
  57.     KMP( "efg", "abcd egfpqr");
  58. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YXAWmt
language:
C (gcc 8.3)
created:
13 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!