模式匹配算法

要求主串a中是否存在子串b，若存在则返回第一次找到的子串的起始位置，若不存在则返回匹配失败。怎么做？

（一）、我们很容易想到的一个算法是这样子的：1、从主串的第一个字符开始进行与子串的匹配，若匹配成功则返回1，表示主串的第一个位置为匹配位置；2、若不成功则将指向主串的指针回溯从主串的第二个字符开始进行与子串的匹配检查，以此类推，直至找到一个能与子串成功匹配的子串位置，返回该位置，或者到达了主串中strlen(a)-strlen(b)位置依然匹配不成功，则返回匹配失败。

（二）、一种改进的模式匹配算法：上面的模式匹配算法每当匹配不成功时都要把标记主串位置的值置为1，这种回溯有时候是不必要的。例：主串为ababcabcacbab，子串为abcac。用i来指示主串位置，用j来指示子串位置。在第一趟匹配中，当i=3,j=3的时候，按照（一）所述的方法，我们要进行的第二趟匹配是：i=2,j=1，但实际上此时我们已经知道i=2对应的元素为b,必然不和a相等，所以这种回溯是不必要的，我们只需直接进行i=3,j=1的比较即可。所以我们现在亟需解决的问题是当主串和子串出现不匹配时，我们应该行子串的哪个位置来和当前的主串进行匹配。
   现在讨论一般的情况。假如主串为“S1S2...Sn”，子串为“P1P2...Pm”。当Si不等于Pj时，接下来我们要将Si和子串的Pk进行比较（当“P1P2...P(k-1)”和“S(i-k+1)S(i-k+2)...S(i-1)"匹配而且不存在其他的下标大于k的子串元素满足这个条件），由于原先本来就有“P(j-k+1)P(j-k+2)...P(j-1)”和“S(i-k+1)S(i-k+2)...S(i-1)"匹配，那么就有“P1P2...P(k-1)”和“P(j-k+1)P(j-k+2)...P(j-1)”匹配，这样我们就可以在只有子串的情况下，得到与主串进行匹配的下一个子串元素。
  定义如下：当j=1时，下一个要进行匹配的子串元素实际上不存在的，我们置为0；
                 当存在"P1P2...P(k-1)”和“P(j-k+1)P(j-k+2)...P(j-1)”匹配而且不存在其他的下标大于k的子串元素满足这个条件时，我们下一个需要匹配的子串元素是k；
                 除去上面两种情况，下一个要匹配的子串元素都是子串的第一个元素。
例如子串“abaabcac”,对应的每个元素在匹配不成功时分别应该匹配的下一个元素下标是：“01122312”。
   寻找下一个预比较下标的代码如下：

void get_next(SString T,int &next[])
{
    int i=1,j=0;
    next[1]=0;
    while(T[i]!='\0')
    {
        if(j==0||T[i]==T[j])
        {
            ++i;
            ++j;
            next[i]=j;
        }
        else
            j=next[j];
    }
}

但是上面的代码存在这样一个问题，例如子串“aaaab”和主串“aaabaaaab”匹配时，当i=4,j=4时，子串与主串不匹配，由寻找下一个子串匹配元素的算法，接下来我们要比较i=4,j=3，但是由于i=4,j=4不匹配，而j=3和j=4指示元素相等，那么i=4,j=3的比较是不必要的。也就是说当Si与Pj不相等时，我们用之前找模式串下一个匹配位置的方法找到下一个预匹配元素k，然后在Pj和Pk不等时，才将k定义为下一个预匹配元素，否则需要继续找。改进后的代码如下：

void get_next(SString T,int &next[])
{
    int i=1,j=0;
    next[1]=0;
    while(T[i]!='\0')
    {
        if(j==0||T[i]==T[j])
        {
            ++i;
            ++j;
            if(T[i]!=T[j])
            {
                next[i]=j;
            }
            else
                next[i]=next[j];
        }
        else
            j=next[j];
    }
}

自己实现的模式匹配代码如下：

#include<stdio.h>
#include<string.h>
#define MaxSubLength 20

void get_next(char* T,int (&next)[MaxSubLength])
{
    int i=1,j=0;
    next[1]=0;
    while(T[i]!='\0')
    {
        if(j==0||T[i]==T[j])
        {
            ++i;
            ++j;
            if(T[i]!=T[j])
            {
                next[i]=j;
            }
            else
                next[i]=next[j];
        }
        else
            j=next[j];
    }
}

int compare(char *s,char *p)
{
    int i=1,j=1,k,q,moveLength;
    int sLength=strlen(s),pLength=strlen(p);
    int nextW[MaxSubLength];
    get_next(p,nextW);
    for(;i<=sLength-pLength+1;)
    {
        j=1;
        k=i;
        while(*(p+j-1)!='\0')
        {
            if(*(s+k-1)!=*(p+j-1))
            {
                break;
            }
            k++;
            j++;
        }
        if(*(p+j-1)=='\0')
        {
            return i;
        }
        else
        {
            q=j;
            j=nextW[j];
            moveLength=q-j;
            i=i+moveLength;
            while(j!=0)
            {
                while(*(p+j-1)!='\0')
                {
                    if(*(s+k-1)!=*(p+j-1))
                        break;
                    k++;
                    j++;
                }
                if(*(p+j-1)=='\0')
                    return i;
                q=j;
                j=nextW[j];
                moveLength=q-j;
                i=i+moveLength;
            }
        }
    }
    return 0;
}
void main()
{
    char s[100],p[20];
    int i;
    printf("请输入主串:\n");
    scanf("%s",s);
    printf("请输入子串:\n");
    scanf("%s",p);
    i=compare(s,p);
    if(i==0)
        printf("没有找到这样的子串！\n");
    else
        printf("子串在主串中的位置为：%d\n",i);
}