1.原始的字符串匹配方法

算法基本思想：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，否则称匹配不成功。

这种匹配方法理解起来很简单，中心思想就是逐个比较字符，每当一趟匹配过程中出现字符不等时，主串的比较指针i需要回溯。时间复杂度为O(n*m)。n为主串的长度，m为匹配的子串的长度。

2.KMP算法

该算法相比原始的字符串匹配方法，其效率更高，省去了一些冗余的、重复的匹配步骤。

算法基本思想：在进行主串和子串匹配过程中，每当一趟匹配过程中出现字符比较不等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离，继续进行比较。

该算法的关键在于当每次匹配不等时，如何确定子串向右“滑动”的距离。其实该“滑动”距离与主串的结构无关，其取决子串的结构中是否存在有重复的部分。假设主串为s1s2…sn，模式串为p1p2…pn，当主串中第i个字符和模式中第j个字符匹配失败时，主串中第i个字符（i指针不回溯）应与模式中哪个字符再比较？

假设此时应与模式中第k（kk也满足下列关系式

                                                           “p1p2…pk-1”=“si-k\+1si-k+2…si-1”

而已经得到的“部分匹配”的结果是

                                                          “pj-k+1pj-k+2…pj-1”=“si-k\+1si-k+2…si-1”

联合以上两式得

                                                         “p1p2…pk-1”= “pj-k+1pj-k+2…pj-1”

上述公式表明，若模式串中存在前k-1个字符和模式串中后k-1个字符相等（前缀和后缀相同），那么当下次匹配时，只需将模式串中第k个字符与主串中的第i个字符比较即可（即下次匹配时j=k），而不用将j回溯到模式串的首字符。由此可导出next[j]=k函数，表明当模式中第j个字符与主串中第i个字符匹配失败时，在模式串中需重新和主串第i个字符进行比较的字符的位置。

                                        ![Center][]

获取模式串各字符的next函数值的代码如下：

void getnext(char s[],int next[])
{
    int i=1,j=0;    
    next[1]=0;    //初始化next函数 
    while (i<s[0])   //s[0]为串的长度 
    {
        if (j==0||s[j]==s[i])   //s[j]为前缀单个字符，s[i]为后缀单个字符，当两者相等时，即前缀和后缀匹配成功，next[i+1]=next[i]+1。
        {                     //或者当j=0时，说明指针j回溯到头仍然无法找到匹配的前缀和后缀，此时next[i+1]=0+1=1； 
            j++;
            i++;
            next[i]=j;
        }
        else
        {
            j=next[j];     //前缀和后缀不等，指针j向前回溯 
        }
    } 
}

完整KMP算法代码如下：

#include <stdio.h>
#include <string.h>
//KMP算法
int next[1000]; 
void getnext(char s[],int *next)
{
    int i=1,j=0;    
    next[1]=0;    //初始化next函数 
    while (i<s[0])   //s[0]为串的长度 
    {
        if (j==0||s[j]==s[i])   //s[j]为前缀单个字符，s[i]为后缀单个字符，当两者相等时，即前缀和后缀匹配成功，next[i+1]=next[i]+1。
        {                     //或者当j=0时，说明指针j回溯到头仍然无法找到匹配的前缀和后缀，此时next[i+1]=0+1=1； 
            j++;
            i++;
            next[i]=j;
        }
        else
        {
            j=next[j];     //前缀和后缀不等，指针j向前回溯 
        }
    } 
} 
int Index(char S[],char s[],int pos)
{
    int i=pos,j=1;
    if (i<1 ||i>S[0]) return 0;
    getnext(s,next);          //获取子串各字符的next函数值 
    while(i<=S[0] && j<=s[0])  
    {
        if (j==0||S[i]==s[j]) //如果对应字符相等则指针同时下移，当模式串的指针j回溯到头，在模式串中找不到与主串第i个字符对应的字符时 
        {                    // 则两指针同时下移 
            i++;
            j++;
        }
        else                 // 匹配字符不等，回溯j指针 
        {
            j=next[j];
        }
    }
    if (j>s[0])         //j大于子串长度，则匹配成功，返回首字符位置 
    {
        return i-s[0];
    }else              //匹配失败，返回0 
    {
        return 0;
    }
}
int main()
{
    char S[1000],s[1000];
    int pos;
    printf("输入主串\n");
    scanf("%s",S+1);
    *S=strlen(S+1);
    printf("输入要查找的串\n");
    scanf("%s",s+1);
    *s=strlen(s+1);
    printf("输入查找的起始位置\n"); 
    scanf("%d",&pos);
    printf("在主串中的位置为%d\n",Index(S,s,pos)); 
    return 0;
}

3.改良的KMP算法

在匹配过程中，KMP算法还是有缺陷的。缺陷在于匹配不符情况下，j指针向前回溯的步骤可能会产生冗余。列如当主串S=“aaaabcde”，模式串s=“aaaaax”时，此时模式串的各字符的next函数值为012345。当匹配到主串第五个字符（i=5），模式串第5个字符（j=5）时，‘b’不等于‘a’，此时j指针就应该回溯。按照next数组，指针j回溯到4，即主串第5个字符与模式串的第4个字符比较，然后不等，指针j又回溯到3，继续比较，一直到指针j回溯到1，发现不等后，i指针才加1。在此过程中，模式串中第1,2,3,4个字符都与第5个字符字符‘a’相等，因此主串第5个字符和模式串中第1,2,3,4进行比较的步骤是多余的。为了改良这个缺陷，我们将首字符的next函数值去取代和它相等字符后续的next函数值，这样模式串各字符新的next函数值分别为000005，就避免了冗余步骤的产生。

获取改良的nextval数组如下：

void getnextval(char s[],int *nextval)
{
    int i=1,j=0;    
    nextval[1]=0;    //初始化nextval函数 
    while (i<s[0])   //s[0]为串的长度 
    {
        if (j==0||s[j]==s[i])   
        {                    
            j++;
            i++;
            if (s[i]!=s[j])   //若当前字符和要回溯的字符不等，则正常记录j值 
            {
                nextval[i]=j;
            }else            //若相等，则当前字符的nextval值等于要回溯字符的nextval值 
            {
                nextval[i]=nextval[j];
            }
        }
        else
        {
            j=nextval[j];     //前缀和后缀不等，指针j向前回溯 
        }
    } 
}