C数据结构 - KMP算法的实现
发布时间:2020-12-16 07:43:36 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 // KMP字符串模式匹配算法// 输入: S是主串,T是模式串,pos是S中的起始位置// 输出: 如果匹配成功返回起始位置,否则返回-1int KMP(PString S,PString T
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 // 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 = %sn",S->str); printf("模式串t = %sn",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,j是模式串的游标 // 这里的主串和模式串都是同一个字符串 if ( - 1 == j || // 如果模式串游标已经回退到第一个字符 pstr -> str[i] == pstr -> str[j]) // 如果匹配成功 { // 两个游标都向前走一步 ++ i; ++ j; // 存放当前的next值为此时模式串的游标值 next[i] = j; } else // 匹配不成功j就回退到上一个next值 { j = next[j]; } } } // KMP字符串模式匹配算法 // 输入: S是主串,pos是S中的起始位置 // 输出: 如果匹配成功返回起始位置,否则返回-1 int KMP(PString S,int pos) { assert(NULL != S); assert(NULL != T); assert(pos >= 0 ); assert(pos < S -> length); if (S -> length < T -> length) return - 1 ; printf( " 主串t = %sn ",S -> str); printf( " 模式串t = %sn ",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 ; } }/* *这就是最后的程序了 * */ 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |