Pattern Matching Algorithms

Naive-Pattern Matching

At first the pattern is set to the left end of the text, and matching process starts. After a mismatch is found, pattern is shifted one place right and a new matching process starts again , and so on.

Best Case

The best case can be found where the time complexity would be :
O(n): where n is the length of the string .
This happens when the first character of the pattern does not exist in the String

Worst Case

This happens when all the characters of the string match the pattern or
if the last character of the string is different [ different infers - could be anything ]
Time complexity: O(mn).

Explaination:At every iteration of n we do m comparision of the Pattern's characters with the String's characters

Knuth-Morris-Pratt Algorithm

The KMP matching algorithm uses degenerating property ( pattern having same sub-patterns appearing more than once in the pattern are ignored )
KMP uses lps array that stands for Longest proper prefix that can hold the array elements that actually have matched to skip those and find the next matching pattern
A.K.A : also called as the longest prefix suffix pattern since the prefix in the pattern is going to be a suffix for the current match , and hence on a mismatch the part that is already matched becomes the prefix and . . .
that much portion is already considered as match with the pattern's prefix and further portion of string is compared
Which essentially stores the Length of the longest proper prefix that was found repeating in the string
amazing_sauce

Code

    

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void computeLPSArray(char *pat, int M,int *lps){
int len=0;
lps[0]=0;
int i=1;

while(i<M){
if(pat[i]==pat[len]){// pattern's CHARACTER MATCH
lps[i++]=++len;
}
else{ // MISMATCH
if(len!=0){ // in any position of the pattern
len=lps[len-1];
}
else{ // in FIRST position of the pattern
lps[i++]=0;
}
}
}
}


void KMPsearch(char *pat,char *txt){
int M=strlen(pat);
int N=strlen(txt);

int *lps=(int*)malloc(sizeof(int)*M);
int j=0,i=0; // iterators for pat amd txt
computeLPSArray(pat,M,lps);

while(i<N){
if(pat[j]==txt[i]){ // Match
i++;
j++;
}
if(j==M){ // end of pattern
printf("Found patten at index: %d",i-j+1);
j=lps[j-1];
}
else if(i<N && pat[j]!=txt[i] ){ // Pure MISMATCH
if(j!=0)
j=lps[j-1];
else
i=i+1;
}
}
free(lps);
}

int main(){

char txt[50],pat[50];

printf("Enter the text: \n");
fgets(txt,50,stdin);
txt[strcspn(txt,"\n")]='\0';

printf("Enter the pattern: \n");
fgets(pat,50,stdin);
pat[strcspn(pat,"\n")]='\0';

KMPsearch(pat,txt);
// getc();
return 0;


}

1D Arrays