How to find the occurrence's of a pattern in a given string Using KMP algorithm?

For finding the pattern in a given string , we are going to use KMP algorithm for individual occurrence of the pattern and print the reference index of the original string.



The function which will find the pattern in a given string :

int KMP(char * str,char* find,int s){
     int sl=strlen(str);
     int fl=strlen(find);
     for(int i=s;i<sl-fl+1;i++){
         int i1=i;
         for(int j=0;j<fl;j++,i1++){
             //cout<<j<<fl<<endl;
             if(j==fl-1)return i;
             if(str[i]!=find[j])break;
         }
     }
     return -1;
 }
For finding all the places (positions/index) where the pattern is present, we have to call the above function repetitively with passing the index from where it has to resume the search as a parameter to the function.
The same is implemented in the function below:
int print_occurence(char* str,char* find){
     int sl=strlen(str);
     int fl=strlen(find);
     int occ=0;
     for(int i=0;i<sl;i++){
         i=KMP(str,find,i);
         if(i==-1){
             //printf("NO pattern found in string\n");
             return occ;
         }
         printf("pattern found at %d position\n",i+1);
         i+=fl;
         occ++;
     }
     return occ;
The driving function:
int main(int argc, char *argv[]) {
     char str[]="hello hello world";
     char find[]="llo";
     printf("Number of occurences found= %d\n",print_occurence(str,find));
     return 0;
 }
Source code C/C++ :

//  https://www.qxcoding.com/ 
include<stdio.h>
include<string.h>        
int KMP(char * str,char* find,int s){
     int sl=strlen(str);
     int fl=strlen(find);
     for(int i=s;i<sl-fl+1;i++){
         int i1=i;
         for(int j=0;j<fl;j++,i1++){
             //cout<<j<<fl<<endl;
             if(j==fl-1)return i;
             if(str[i]!=find[j])break;
         }
     }
     return -1;
 }
 int print_occurence(char* str,char* find){
     int sl=strlen(str);
     int fl=strlen(find);
     int occ=0;
     for(int i=0;i<sl;i++){
         i=KMP(str,find,i);
         if(i==-1){
             //printf("NO pattern found in string\n");
             return occ;
         }
         printf("pattern found at %d position\n",i+1);
         i+=fl;
         occ++;
     }
     return occ;
 }
 int main(int argc, char *argv[]) {
     char str[]="hello hello world";
     char find[]="llo";
     printf("Number of occurences found= %d\n",print_occurence(str,find));
     return 0;
 }

if any doubts or queries please comment 🙂

Comments

  1. Casino and Table Games Near Me - The MJ Hub
    The best and worst casinos near me 충청남도 출장샵 on our list · Hollywood 춘천 출장마사지 Casino 과천 출장마사지 at Charles Town 거제 출장안마 Races and Casinos · Sugarhouse at Chittenango Casino · 창원 출장안마 Harrah's Resort Tunica

    ReplyDelete

Post a Comment

Popular posts from this blog

Python and C++ program to implement multiplication of 2d array (Matrix multiplication)

What is AI (Artificial Intelligence )? and its characteristics

How to find and replace a node in Linked List