C语言-字符串匹配-KMP算法及next数组求解和运用实例

末蓝、 2022-07-18 01:52 99阅读 0赞

**1. 目标**

求解一个目标串的next数组，运用next数组寻找s串中是否有T串，没有返回-1，如果有返回s的下标值。

**2. 运行示例**

如下：

![Center][]

**3.代码分析**

对next数组的求解代码比较难以理解。 可以参考 北京小王子 的微博，写的比较详细。[点击打开链接][Link 1]（http://www.cnblogs.com/tangzhengyue/p/4315393.html）

**4.源代码**

<span style="font-size:14px;">#include<stdio.h>
    #define Tarray_size 255
    #define title "------------------------------Life is a fight!------------------------------------"
    
    typedef struct KMP {
        int qty;
        char* str;
    } kmp;
    
    //create next array
    void Getnext(kmp* T, int* next)
    {
    	int i=-1; //prefix
    	int j=0;//suffix
    	next[0]=-1;//next等于-1表示，i需要+1，即s数组中索引要向后挪一位，例如在T[0]!=s[0]时，需要比较T[0]和s[1]
    	while(j<T->qty)
    	{
    		if(-1==i||*(T->str+i)==*(T->str+j))
    		{
    			i++;
    			j++;
    			if(*(T->str+i)!=*(T->str+j))//这个if语言的判断不是必须，但是可以优化规则，提高效率
                    next[j]=i;
                else
                    next[j]=next[i];
    		}
    		else
    		{
    			i=next[i];//i 回溯
    		}
    	}
    }
    
    //在字符串s， 第pos个位置开始寻找t
    //找到返回位置i,否则返回-1
    int Index_kmp(kmp* s, kmp* t, int* next, int pos)
    {
        int i=pos;
        int j=0;
    
        while(i<s->qty && j<t->qty)
        {
            if(-1==j||*(s->str+i)==*(t->str+j))
            {
                j++;
                i++;
            }
            else
                j=next[j];
        }
        if(j>=t->qty)
            return i-t->qty;
        else
            return -1;
    }
    int main(void)
    {
        kmp *s, *T;
        int next[Tarray_size];
        char *s1, *t1;
        int i1, i2;
    
        s1="aaaabcaaacaaaaaabc";
        t1="aaaaaab";
    
        s=(kmp*)malloc(sizeof(kmp));
        T=(kmp*)malloc(sizeof(kmp));
        s->str=s1;
        T->str=t1;
        s->qty=0;
        T->qty=0;
    
        while((*s1)!='\0')//计算s字符串的长度
        {
            (s->qty)++;
            s1++;
        }
        while(*t1!='\0')//计算T串的长度
        {
            (T->qty)++;
            t1++;
        }
    
        printf("%s\n\n",title);
        printf("Si:   ");
        for(i1=0;i1<s->qty;i1++)//打印T数组下标
            printf("%2d ", i1);
        printf("\n");
        printf("S:    ");
        for(i1=0;i1<s->qty;i1++)//打印T串
            printf("%2c ", *(s->str+i1));
        printf("\n\n");
        printf("Ti:   ");
        for(i1=0;i1<T->qty;i1++)//打印T数组下标
            printf("%2d ", i1);
        printf("\n");
        printf("T:    ");
        for(i1=0;i1<T->qty;i1++)//打印T串
            printf("%2c ", *(T->str+i1));
        printf("\nNext: ");
        Getnext(T,next);//生成next数组
        for(i1=0;i1<T->qty;i1++)//打印next数组
            printf("%2d ",*(next+i1));
        i2=Index_kmp(s,T,next,0);//利用next数组在s串中寻找T串的位置
        printf("\n\nT position in s: %d\n",i2);
        free(T);free(s);
        return 0;
    }</span>

[Center]: /images/20220717/45d2a1bf413a4806a37f666210938f5e.png
[Link 1]: http://www.cnblogs.com/tangzhengyue/p/4315393.html