// KMP字符串模式匹配算法 // 输入: S是主串,T是模式串,pos是S中的起始位置 // 输出: 如果匹配成功返回起始位置,否则返回-1 int KMP(PString S, PString T, int pos) { assert(NULL != S); assert(NULL != T); assert(pos >= 0); assert(pos < S->length); if (S->length < T->length) return -1; printf("主串\t = %s\n", S->str); printf("模式串\t = %s\n", T->str); int *next = (int *)malloc(T->length * sizeof(int)); // 得到模式串的next数组 GetNextArray(T, next); int i, j; for (i = pos, j = 0; i < S->length && j < T->length; ) { // i是主串游标,j是模式串游标 if (-1 == j || // 模式串游标已经回退到第一个位置 S->str[i] == T->str[j]) // 当前字符匹配成功 { // 满足以上两种情况时两个游标都要向前进一步 ++i; ++j; } else // 匹配不成功,模式串游标回退到当前字符的next值 { j = next[j]; } } free(next); if (j >= T->length) { // 匹配成功 return i - T->length; } else { // 匹配不成功 return -1; } } // 得到字符串的next数组 void GetNextArray(PString pstr, int next[]) { assert(NULL != pstr); assert(NULL != next); assert(pstr -> length > 0 ); // 第一个字符的next值是-1,因为C中的数组是从0开始的 next[ 0 ] = - 1 ; for ( int i = 0 , j = - 1 ; i < pstr -> length - 1 ; ) { // i是主串的游标,j是模式串的游标 // 这里的主串和模式串都是同一个字符串 if ( - 1 == j || // 如果模式串游标已经回退到第一个字符 pstr -> str[i] == pstr -> str[j]) // 如果匹配成功 { // 两个游标都向前走一步 ++ i; ++ j; // 存放当前的next值为此时模式串的游标值 next[i] = j; } else // 匹配不成功j就回退到上一个next值 { j = next[j]; } } } #include < stdio.h > #include < stdlib.h > #include < assert.h > #include < string .h > #define MAX_LEN_OF_STR 30 // 字符串的最大长度 typedef struct String // 这里需要的字符串数组,存放字符串及其长度 { char str[MAX_LEN_OF_STR]; // 字符数组 int length; // 字符串的实际长度 } String, * PString; // 得到字符串的next数组 void GetNextArray(PString pstr, int next[]) { assert(NULL != pstr); assert(NULL != next); assert(pstr -> length > 0 ); // 第一个字符的next值是-1,因为C中的数组是从0开始的 next[ 0 ] = - 1 ; for ( int i = 0 , j = - 1 ; i < pstr -> length - 1 ; ) { // i是主串的游标,j是模式串的游标 // 这里的主串和模式串都是同一个字符串 if ( - 1 == j || // 如果模式串游标已经回退到第一个字符 pstr -> str[i] == pstr -> str[j]) // 如果匹配成功 { // 两个游标都向前走一步 ++ i; ++ j; // 存放当前的next值为此时模式串的游标值 next[i] = j; } else // 匹配不成功j就回退到上一个next值 { j = next[j]; } } } // KMP字符串模式匹配算法 // 输入: S是主串,T是模式串,pos是S中的起始位置 // 输出: 如果匹配成功返回起始位置,否则返回-1 int KMP(PString S, PString T, int pos) { assert(NULL != S); assert(NULL != T); assert(pos >= 0 ); assert(pos < S -> length); if (S -> length < T -> length) return - 1 ; printf( " 主串\t = %s\n " , S -> str); printf( " 模式串\t = %s\n " , T -> str); int * next = ( int * )malloc(T -> length * sizeof ( int )); // 得到模式串的next数组 GetNextArray(T, next); int i, j; for (i = pos, j = 0 ; i < S -> length && j < T -> length; ) { // i是主串游标,j是模式串游标 if ( - 1 == j || // 模式串游标已经回退到第一个位置 S -> str[i] == T -> str[j]) // 当前字符匹配成功 { // 满足以上两种情况时两个游标都要向前进一步 ++ i; ++ j; } else // 匹配不成功,模式串游标回退到当前字符的next值 { j = next[j]; } } free(next); if (j >= T -> length) { // 匹配成功 return i - T -> length; } else { // 匹配不成功 return - 1 ; } }/* *这就是最后的程序了 * */
