Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<string.h>
- #include<stdlib.h>
- #include<stdio.h>
- #define MAX_LEN 500
- #define MAX_PAT_LEN 10
- typedef struct kmp_wrapper{
- char test_string[MAX_LEN];
- char pattern[MAX_PAT_LEN];
- int h[MAX_PAT_LEN];
- }KMP;
- int kmp(KMP *kmp_testcase);
- void pattern_perprocess(char* pattern,int* kmp_table,int len);
- int kmp(KMP *kmp_testcase){
- int len_test_string = strlen(kmp_testcase->test_string);
- int len_pattern = strlen(kmp_testcase->pattern);
- int pos_test_string = 0;
- int pos_pattern = 0;
- int occ_count = 0;
- int pos = 0;
- pattern_preprocess(kmp_testcase->pattern,kmp_testcase->h,len_pattern);
- int i=0;
- while(pos_test_string<len_test_string){
- if(pos_pattern == len_pattern){
- pos_pattern = 0;
- pos_test_string++;
- }
- while( pos_pattern<len_pattern && kmp_testcase->test_string[pos_test_string]==kmp_testcase->pattern[pos_pattern]){
- pos_test_string++;
- pos_pattern++;
- //printf("pos1 = %d pos_pattern = %d\n",pos_test_string,pos_pattern);
- if(pos_pattern == len_pattern){
- pos_pattern = kmp_testcase->h[len_pattern-1];
- pos_pattern++;
- occ_count++;
- }
- }
- if(kmp_testcase->test_string[pos_test_string]!=kmp_testcase->pattern[pos_pattern]) {
- if(kmp_testcase->h[pos_pattern]!=-1){
- pos_pattern = kmp_testcase->h[pos_pattern];
- }
- else{
- pos_pattern = 0;
- pos_test_string++;
- }
- }
- }
- return occ_count;
- }
- void pattern_preprocess(char *test_string,int* kmp_table,int len_string){
- //set temp[0] to -1 and temp[1] to zero
- /**
- * 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]
- */
- kmp_table[0] = -1; /**As no string starts before this*/
- kmp_table[1] = 0; /**As no perfix exists*/
- int pos = 2;
- int prev_longest_prefix_len = 0; /**Is actually the index*/
- while(pos<len_string){
- if(test_string[pos-1]==test_string[prev_longest_prefix_len]){
- prev_longest_prefix_len++;
- kmp_table[pos] = prev_longest_prefix_len;
- pos++;
- }
- else if(prev_longest_prefix_len>0){
- prev_longest_prefix_len = kmp_table[prev_longest_prefix_len];
- }
- else{
- kmp_table[pos] = 0;
- pos++;
- }
- }
- }
- int main(){
- KMP *kmp_testcase = (KMP*)malloc(sizeof(KMP));
- printf("Enter the test string:\n");
- scanf("%s",kmp_testcase->test_string);
- printf("Enter the pattern string:\n");
- scanf("%s",kmp_testcase->pattern);
- printf("Number of occurences of pattern %s in %s are %d\n",kmp_testcase->pattern,kmp_testcase->test_string,kmp(kmp_testcase));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement