Knuth Morris Pratt ( KMP ) algorithm in c
On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
code in C:#include<stdio.h> #include<string.h> char txt[100],pat[100]; int M ,N ,lps[100],j=0,i=0; void computeLPSArray() { int len = 0, i; lps[0] = 0; i = 1; while(i < M) { if(pat[i] == pat[len]) { len++; lps[i] = len; i++; } else { if( len != 0 ) len = lps[len-1]; else { lps[i] = 0; i++; } } } } void KMPSearch() { int j=0,i=0; M = strlen(pat); N = strlen(txt); computeLPSArray(); while(i < N) { if(pat[j] == txt[i]) { j++; i++; } if (j == M) { printf("Found pattern at index %d \n", i-j); j = lps[j-1]; } else if(pat[j] != txt[i]) { if(j != 0) j = lps[j-1]; else i = i+1; } } } int main() { printf("\n ENTER THE TEXT : "); gets(txt); printf("\n ENTER THE PATTERN : "); gets(pat); KMPSearch(); return 0; }output:-
ENTER THE TEXT : Welcome To CampusCoke ENTER THE PATTERN : C Found pattern at index 11 Found pattern at index 17 --------------------------------
0 comments: