关于BF算法和KMP算法

零度非安全

这两个算法可是弄了我好久的，终于搞明白了，出此贴温习下

//Brute-Force算法
int index(SqString s,SqString t)                    //目标串s，模式串t
{
        int i = 0,j = 0;                                                                //指针下标i标志s串，指针下标j标志t串
        while(i < s.length && j < t.length)             //当各自指针下标小于各自的串的长度时，则执行该循环体
        {
                if(s.data[i] == t.data[j])                  //如相等则继续匹配下一个字符
                {
                        i++;                                    //主串和子串依次匹配下一个字符
                        j++;
                }
                else                                        //如果不相等主串、子串指针回溯重新开始下一次匹配
                {
                        i = i - j + 1;                          //主串从下一个位置开始匹配
                        j = 0;                                  //子串从头开始匹配
                }
        }
        if(j >= t.length)
                return(i - t.length);                       //返回匹配的第一个字符的下标
        else
                 return(-1);                                 //模式匹配不成，返回-1
}
//总结：这个算法简单，易于理解，但效率不高，主要原因是：主串指针i在若干个字符序列比较相等后，若有一个字符比较不相等，仍需回溯(即i = i - j + 1)
//该算法在最好的情况下的时间复杂度为O(m)，即主串的前m个字符等于模式串的m个字符。在最坏的情况下的时间复杂度为O(nm)

//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各增1
                }
                else j = next[j];                                 //i不变，j后退
        }
        if(j >= t.length)
                return(i - t.length);
        else
                return(-1);
}


//求next[]的值
void GetNext(SqString t.int next[])                         //对模式串t，求next[]值
{
        int j,k;
        j = 0;k = -1;next[0] = -1;
        while(j < t.length - 1)
        {
                if(k == -1 || t.data[j] == t.data[k])              //k为-1或比较的字符相等时
                {
                        j++;k++;                                     
                        next[j] = k;
                }
                else k = next[k];
        }
}
//说明：上述定义的next[]在某些情况下仍有缺陷，例如，设主串s为"aaabaaaab",模式串t为"aaaab"

//修正后的求nextval数组的算法如下：
void GetNextval(SqString t,int nextval[])
{
        int j = 0,k = -1;
        nextval[0] = -1;
        while(j < t.length)
        {
                if(k == -1 || t.data[j] == t.data[k])
                {
                        if(t.data[j]!=t.data[k])
                                nextval[j] = k;
                        else
                                nextval[j] = nextval[k];
                }
                else
                        k = nextval[k];
         }
}

//修正后的KMP算法如下：
int KMPIndex(SqString s,SqString t)
{
        int nextval[MaxSize],i = 0,j = 0;
        GetNextval(t,nextval);
        while(i < s.length && j < t.length)
        {
                if(j == -1 || s.data[i] == t.data[j])
                {
                        i++;
                        j++;
                }
                else
                        j = nextval[j];
        }
        if(j >= t.length)
                return(i - t.length);
        else
                return(-1);
}

～风介～

之前学过， 现在忘记光光了~~

淫令天下

支持楼主！

qunianjinri

修正后的GetNextval 函数wile循环里少了个 j++ ,k++.另外t.length-1
     while(j < t.length - 1)
        {
                if(k == -1 || t.data[j] == t.data[k])
                {
                        j++;
                        k++;
                        if(t.data[j]!=t.data[k])
                                nextval[j] = k;
                        else
                                nextval[j] = nextval[k];
                }
                else
                        k = nextval[k];
        }

鱼C工作室.YCGZS

感谢分享

孤心傲

就是来顶 支持

斩月and剡月

就是来顶 支持:lol:

磨牙耗子

程序可以正常运行，还有点地方可能没有考虑到得，大手子指点下

#include<stdio.h>      
                                                 //为什么没有用strlen函数的有文件#include<string.h>也可以实现。
int main()
{
        char str[]="fishcshe.com",str2[50];
        int i,count,j,blag,m,n;
        printf("请输入要查找的字符串str2[]: ");
        gets(str2);
        m=strlen(str);
        n=strlen(str2);
        for(i=0;i < m;i++)         //用for循环会出现当子串第一次查找完成后会继续遍历查找后面的字符串，1.会增加运算量；2.但是
        {                                   //可以规避当主串中重复出现子串的现象，并以最后一个出现的子串的首字符位置作为输出位置。
                count=0;         
                for(j=        0;j<n;j++)
                {
                        if(str[i+j]==str2[j])
                        {
                                count++;
                                if(count==n)
                                {
                                        blag=  i;
                                        break;
                                }
                        }
                        else
                                break;
                }                       
        }
        if(blag>0)
       
                        printf("子串在主串第%d位存在\n",blag+1);
        else
                printf("子串不在主串中\n");
}