- // 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 ;
- }
- }/*
- *这就是最后的程序了
- *
- */
来源: http://www.phpxs.com/code/1004084/