Advertisement
Guest User

KMP implementation

a guest
Jul 2nd, 2015
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.86 KB | None | 0 0
  1. #include<string.h>
  2. #include<stdlib.h>
  3. #include<stdio.h>
  4. #define MAX_LEN 500
  5. #define MAX_PAT_LEN 10
  6.  
  7. typedef struct kmp_wrapper{
  8.     char test_string[MAX_LEN];
  9.     char pattern[MAX_PAT_LEN];
  10.     int h[MAX_PAT_LEN];
  11. }KMP;
  12.  
  13. int kmp(KMP *kmp_testcase);
  14. void pattern_perprocess(char* pattern,int* kmp_table,int len);
  15.  
  16. int kmp(KMP *kmp_testcase){
  17.     int len_test_string = strlen(kmp_testcase->test_string);
  18.     int len_pattern = strlen(kmp_testcase->pattern);
  19.     int pos_test_string = 0;
  20.     int pos_pattern = 0;
  21.     int occ_count = 0;
  22.     int pos = 0;
  23.     pattern_preprocess(kmp_testcase->pattern,kmp_testcase->h,len_pattern);
  24.     int i=0;
  25.     while(pos_test_string<len_test_string){
  26.         if(pos_pattern == len_pattern){
  27.             pos_pattern = 0;
  28.             pos_test_string++;
  29.         }
  30.         while( pos_pattern<len_pattern && kmp_testcase->test_string[pos_test_string]==kmp_testcase->pattern[pos_pattern]){
  31.             pos_test_string++;
  32.             pos_pattern++;
  33.             //printf("pos1 = %d pos_pattern = %d\n",pos_test_string,pos_pattern);
  34.             if(pos_pattern == len_pattern){
  35.                 pos_pattern = kmp_testcase->h[len_pattern-1];
  36.                 pos_pattern++;
  37.                 occ_count++;
  38.             }
  39.         }
  40.         if(kmp_testcase->test_string[pos_test_string]!=kmp_testcase->pattern[pos_pattern]) {
  41.             if(kmp_testcase->h[pos_pattern]!=-1){
  42.                 pos_pattern = kmp_testcase->h[pos_pattern];
  43.             }
  44.             else{
  45.                 pos_pattern = 0;
  46.                 pos_test_string++;
  47.             }
  48.         }
  49.     }
  50.     return occ_count;
  51. }
  52.  
  53. void pattern_preprocess(char *test_string,int* kmp_table,int len_string){
  54.     //set temp[0] to -1 and temp[1] to zero
  55.     /**
  56.      * Here the h[i] represents the size of the longest proper prexfix of W[1..i-1] which is a suffix of W[1..i-1]
  57.      */
  58.     kmp_table[0] = -1; /**As no string starts before this*/
  59.     kmp_table[1] = 0; /**As no perfix exists*/
  60.     int pos = 2;
  61.     int prev_longest_prefix_len = 0; /**Is actually the index*/
  62.     while(pos<len_string){
  63.         if(test_string[pos-1]==test_string[prev_longest_prefix_len]){
  64.             prev_longest_prefix_len++;
  65.             kmp_table[pos] = prev_longest_prefix_len;
  66.             pos++;
  67.         }
  68.         else if(prev_longest_prefix_len>0){
  69.             prev_longest_prefix_len = kmp_table[prev_longest_prefix_len];
  70.         }
  71.         else{
  72.             kmp_table[pos] = 0;
  73.             pos++;
  74.         }
  75.     }
  76. }
  77. int main(){
  78.     KMP *kmp_testcase = (KMP*)malloc(sizeof(KMP));
  79.     printf("Enter the test string:\n");
  80.     scanf("%s",kmp_testcase->test_string);
  81.     printf("Enter the pattern string:\n");
  82.     scanf("%s",kmp_testcase->pattern);
  83.     printf("Number of occurences of pattern %s in %s are %d\n",kmp_testcase->pattern,kmp_testcase->test_string,kmp(kmp_testcase));
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement