字符串的模式匹配算法

//字符串的模式识别算法
//BF算法   标签:暴力匹配算法,回溯法,穷举法的应用  思想:主串指针回溯
int IndexString(SqString S,SqString T)
{
    int i=0,j=0;
    //这里面有一个代码的技巧 ,遇到两个有长度的序列比较,用while,判断他们长度,出去不符合长度
    while (i<S.length&&j<T.length)  //当i,j小于长度时,循环
    {
        if (S.data[i]==T.data[j])
        {
            i++;j++;
        }
        else   //不相等,主串指针i回溯到下一个结点,j回到0
        {
            i=i-j+1;
            j=0;
        }
    }//while结束
    if (j>=T.length) //匹配成功
        return i-T.length;   //返回子串在主串中第一次出现的位置
    else
        return -1; //匹配失败,返回-1
}
//KMP算法  1.next数组生成,2.根据next数组匹配    解决BF算法的主串指针回溯问题
//由模式串生成next数组
void GetNext(SqString T,int next[])
{
    int j=0,k=-1;next[0]=-1;
    while (j<T.length-1)
    {
        if (k==-1||T.data[k])
        {
            j++;k++;
            next[j]=k;
        }
        else
            k=next[k];
    }
}
//KMP算法
int KMPIndex(SqString S,SqString T)
{
    int next[MaxSize],i=0,j=0;
    GetNext(T,next);
    while (i<S.length && j<T.length)
    {
        if (j==-1||S.data[i]==T.data[j])
        {
            i++;j++;    //i++,j++
        }
        else
            j=next[j];   //i不变,j后退
    }
    if (j>=T.length)
        return i-T.length;  //匹配成功,返回模式串在主串中的位置
    else
        return -1;
}