fork download
copy 
  1. #include <stdlib.h>
  2. #include <string.h>
  3.  
  4. int kmp(char substr[], char str[])
  5. {
  6.     int i, j, N, M;
  7.  
  8.     N = strlen(str);
  9.     M = strlen(substr);
  10.  
  11.     int *d = (int*)malloc(M * sizeof(int));
  12.     d[0] = 0;
  13.  
  14.     for(i = 0, j = 0; i < M; i++)
  15.     {
  16.         while(j > 0 && substr[j] != substr[i])
  17.         {
  18.             d[j] = i - 1;
  19.         }
  20.  
  21.         if(substr[j] == substr[i])
  22.         {
  23.             j++;
  24.             d[i] = j;
  25.         }
  26.     }
  27.  
  28.     for(i = 0, j = 0; i < N; i++)
  29.     {
  30.         while(j > 0 && substr[j] != str[i])
  31.         {
  32.             d[j] = i - 1;
  33.         }
  34.  
  35.         if(substr[j] == str[i])
  36.         {
  37.             j++;
  38.         }
  39.  
  40.         if(j == M)
  41.         {
  42.             free(d);
  43.             return i- j + 1;
  44.         }
  45.     }
  46.  
  47.     free(d);
  48.  
  49.     return -1;
  50. }
  51.  
  52. int main(void)
  53. {
  54.     char substr[] = "World",
  55.         str[] = "Hello World!\r\n";
  56.  
  57.     int pos = kmp(substr, str);
  58.  
  59.     return 0;
  60. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FVAzU
language:
C (gcc 8.3)
created:
13 years 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!