题解：字符串模式匹配

Guderian出品

前置知识：KMP算法

说明

模式匹配是指给定主串t和子串s， 在主串t中寻找子串s的过程， 其中s称为模式。 如果匹配成功， 返回s在t中的位置， 否则返回-1。

分析

KMP算法用 next 数组对匹配过程进行了优化。 KMP 算法的伪代码描述如下：

1． 在串t和串s中， 分别设比较的起始下标i=j=0。

2． 如果串t和串s都还有字符， 则循环执行下列操作：

（1） 如果j=-l或者t[i]=s[j]， 则将i和j分别加1，继续比较t和s的下一个字符；

（2） 否则， 将j向右滑动到next[j]的位置， 即j=next[j]。

3． 如果s中所有字符均已比较完毕， 则返回匹配的起始位置（从1开始） ； 否则返回-1．其中， next数组根据子串s求解。 求解next数组的代码已由get_next函数给出。

实现

（1）常量和变量说明

t，s：长度为lt和ls的字符串

next[]：next数组，长度为ls

（2）C语言程序

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

/*求 next[]的值*/
void get_next( int *next, char *s, int ls) {
    int i=0, j=-1;
    next[0]=-1;/*初始化 next[0]*/
    while(i < ls){/*还有字符*/
        if(j==-1 || s[i]==s[j]){/*匹配*/
            j++;
            i++;
            if(s[i]==s[j])
                next[i]=next[j];
            else
                next[i]=j;
        }
        else
            j=next[j];
    }
}

int kmp( int *next, char *t,char *s, int lt, int ls )
{
    int i= 0,j =0 ;
    while (i < lt && j < ls)
    {
        if( j==-1 || t[i]==s[j] )
        {
            i ++ ;
            j ++ ;
        }
        else
            j=next[j];
    }
    if (j >= ls)
        return i+1-ls;
    else
        return -1;
}

（3）复杂度分析

• 时间复杂度：$O(ls+lt)$
  • 预处理$ O(ls)$，匹配$ O(lt)$
• 空间复杂度：$O(ls)$