#include<stdio.h> #include<string.h> typedef char Elemtype; //生成前缀的长度 void GenPreFix( Elemtype *Pattern, int *PreFix ) { int LOLP = 0; //length of largest prefix int NOCM; //number of character matched int Patlen = strlen(Pattern); PreFix[0] = -1; PreFix[1] = 0; for( NOCM=2; NOCM<Patlen+1; NOCM++ ) { while( LOLP>0 && Pattern[LOLP] != Pattern[NOCM-1] ) //cursor -1 LOLP = PreFix[LOLP]; if( Pattern[LOLP] == Pattern[NOCM-1] )// -1 LOLP++; PreFix[NOCM] = LOLP; } } //KMP匹配函数 void KmpStrMatching( Elemtype *Target, Elemtype *Pattern, int *prefix ) { int Patlen = strlen( Pattern ); int Tarlen = 0; //记录已查找的目标串长度 int NextLength = 0; int flag = 0; //标记是否匹配成功过 while( '\0' != *Target ) { for( int i=0; i<Patlen; i++ ) if( *(Target+i) != *(Pattern+i) ) break; if( i == Patlen ) { printf("位置%d处匹配成功!\n", Tarlen+1); flag = 1; } NextLength = i - prefix[i]; // i--已经匹配成功的字符数, i=0 --- prefix[0]=-1 表示没匹配到任何字符,向后移一位 Target = Target + NextLength; Tarlen += NextLength; } if( 0 == flag ) printf("匹配不成功!\n"); } int main() { Elemtype TargetStr[100], PatternStr[20]; int prefix[21]; //下表从1到20有效 printf("请输入目标字符串:\n"); gets(TargetStr); printf("请输入模式字符串:\n"); gets(PatternStr); GenPreFix( PatternStr, prefix ); // 检测通过 KmpStrMatching( TargetStr, PatternStr, prefix ); return 0; }