串的模式匹配（KMP算法）

【问题描述】

串的模式匹配算法实现（KMP算法）

【输入形式】

第一行输入主串s；

第二行输入模式串t；

第三行输入起始位置pos；

【输出形式】

输出模式串t的next值（以空格分隔）

输出模式匹配结果

【样例输入1】

ababcabcacbab

abcac

1

【样例输出1】

-1 0 0 0 1

6

BF算法的原理简单但效率较低。原因是 i 和 j 的回溯，即在某趟匹配失败后，对于 s 串要回溯到本趟开始字符的下一个字符，t 串要回溯到第一个字符。然而这些回溯很多是不必要的。

  改进的模式匹配过程由Knuth，Morris，Pratt同时设计的，简称KMP算法，其特点是，每当一趟匹配过程中Si和Tj匹配失败后，指针i不动，模式t向右“滑动”，使Tk和Si对准继续向右比较。

比较过程如下：

第一趟比较，主串，子串均从起始位置开始比较，匹配失败时主串 i=2，子串 j=2。

 第二趟比较，主串 i 保持不动，不回溯，子串向前滑动至 j=0的位置，开始对应字符的比较。一直到发生匹配失败时，主串 i=6，子串 j=4。

 我们将模式串的每个位置匹配失败时滑动的位置计算出来，放到一个 next数组中，当发生匹配失败时直接拿出来用即可，Nex数组的求解过程分三种情况：

这里将 next[0] 设置为-1。

 next数组的计算：

void getNext(SqString *t,int next[]){
    int i=0,j=-1;
    next[0]=-1;
    while(i<t->length)
    {
        if((j==-1)||(t->data[i]==t->data[j]))
        {
            i++;
            j++;
            next[i]=j;
        }
        else j=next[j];
    }
}

KMP算法：

int indexKMP(SqString *s,SqString *t,int start,int next[]){
    int i=start-1,j=0;
    while(i<s->length&&j<t->length)
    {
        if(i==-1||s->data[i]==t->data[j])   //*s 和 t 对应字符相等，比较下一个字符
    {
        i++;
        j++;
    }
    else j=next[j];     //开始下一次匹配，子串指针 j 移动到下一个比较位置
    }

    if(j>=t->length)
        return(i-t->length);
    else
        return 0;
}

完整代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>

#define INITSIZE 1000
#define INCRE 20
#define OK 1
#define ERROR 0

typedef struct{
  char* data;
  int length,stringsize;
}SqString;

//串初始化
int initString(SqString *S){
    S->data=(char *)malloc(INITSIZE*sizeof(char));
    if(!S->data)
        return ERROR;
    S->length=0;
    S->data[0]='\0';
    S->stringsize=INITSIZE;
    return OK;
}

//串赋值
int strAssign(SqString *s, char *str ){
    int i=0;
    while(*str!='\0')
        s->data[i++]=*str++;
    s->data[i]='\0';
    s->length=i;
    return OK;
}
//模式匹配KMP算法
int indexKMP(SqString *s,SqString *t,int start,int next[]){
    int i=start-1,j=0;
    while(i<s->length&&j<t->length)
    {
        if(i==-1||s->data[i]==t->data[j])
    {
        i++;
        j++;
    }
    else j=next[j];
    }

    if(j>=t->length)
        return(i-t->length);
    else
        return 0;
}
//求取模式串next值
void getNext(SqString *t,int next[]){
    int i=0,j=-1;
    next[0]=-1;
    while(i<t->length)
    {
        if((j==-1)||(t->data[i]==t->data[j]))
        {
            i++;
            j++;
            next[i]=j;
        }
        else j=next[j];
    }
}

int main(){
//使用KMP算法完成串的模式匹配
    SqString s,t;
    int start,i;
    int next[1000];
    char str[1000];
    initString(&s);
    initString(&t);
    scanf("%s",&str);
    strAssign(&s,str);
    scanf("%s",&str);
    strAssign(&t,str);
    getNext(&t,next);
    scanf("%d",&start);
    for(i=0;i<t.length;i++)
    {
        printf("% d",next[i]);
    }
    printf("\n");
    printf("%d ",indexKMP(&s,&t,start,next));
    return 0;
}

运行结果如下：