KMP String Matching Algorithm | |||
| |||
Here's the implemented algorithm. //////////////////////////////////////////////////////////////////// // programmed by Kurapa Chunun Kang (kurapa@kurapa.com) #ifndef __GLOBAL_H__ #define __GLOBAL_H__ #define MAX_STRING_SIZE 100 #define MAX_PATTERN_SIZE 100 int g_failure[MAX_PATTERN_SIZE]; int pattern_matching(char *str, char *pat); void make_failure(char *pat); ////////////////////////////////////////////////////////////// #endif // __GLOBAL_H__ #include <stdlib.h> #include <stdio.h> #include <string.h> // knuth,morris,pratt string matching algorithm int pattern_matching(char *str, char *pat) { int i = 0, j = 0; // index int intStrLen = strlen(str); int intPatLen = strlen(pat); // debug // printf("intStrLen = %d intPatLen = %d ", intStrLen, intPatLen); // index should be longer than intStrLen & intPatLen while ((i < intStrLen) && (j < intPatLen)) { if (str[i] == pat[j]) { i++; j++; } else if (j == 0) i++; else j = g_failure[j-1] + 1; } return ((j == intPatLen) ? (i - intPatLen) : -1); } void make_failure(char *pat) // create failure function for target string { int j = 0; int intPatLen = strlen(pat); g_failure[j] = -1; // the first value should be -1 int i = 0; for ( j=1; j<intPatLen; j ++) { i = g_failure[j - 1]; while ((pat[j] != pat[i+1]) && (i >= 0)) { i = g_failure[i]; } /// end while if (pat[j] == pat[i+1]) g_failure[j] = i+1; else g_failure[j] = -1; } // end for // below is for debug printf( "g_failure[]={"); for (j = 0; j < intPatLen; j ++) { if (j) printf( ",%d", g_failure[j]); else printf("%d", g_failure[j]); } printf( "} - where pattern=%s ", pat); } int main(int argc, char **argv) { char string[] = "aababaaasdasdasdasdcas"; char *pattern = "ababaa"; int result = 0; make_failure(pattern); result = pattern_matching(string, pattern); // debug printf ("string is %s ", string); printf ("pattern is %s ", pattern); printf ("result = %d ", result); make_failure(pattern); pattern = "aabba"; make_failure(pattern); pattern = "abababab"; make_failure(pattern); pattern = "ababbaab"; make_failure(pattern); return 0; } /* run result Microsoft Windows XP [Version 5.1.2600] (C) Copyright 1985-2001 Microsoft Corp. Z:내 문서Debug>kmp g_failure[]={-1,-1,0,1,2,0} - where pattern=ababaa intStrLen = 22 intPatLen = 6 string is aababaaasdasdasdasdcas pattern is ababaa result = 1 g_failure[]={-1,-1,0,1,2,0} - where pattern=ababaa g_failure[]={-1,0,-1,-1,0} - where pattern=aabba g_failure[]={-1,-1,0,1,2,3,4,5} - where pattern=abababab g_failure[]={-1,-1,0,1,-1,0,0,1} - where pattern=ababbaab Z:내 문서Debug> */ Tags: Access Key Amazon Amazon CloudFront C++ Morris Pratt String Matching Algorithm String Search Algorithm | |||
| |||
| |||
Login for comment |
SIMILAR POSTS URL Encode, Decode function for MFC |