论坛 › 数据结构与算法 › 关于BF算法和KMP算法

零度非安全 发表于 2015-10-24 20:09:47

关于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 == t.data)                  //如相等则继续匹配下一个字符
                {
                        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,i = 0,j = 0;
        GetNext(t,next);
        while(i < s.length && j < t.length)
        {
                if(j == -1 || s.data == t.data)
                {
                        i++;
                        j++;                                          //i,j各增1
                }
                else j = next;                                 //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 = -1;
        while(j < t.length - 1)
        {
                if(k == -1 || t.data == t.data)            //k为-1或比较的字符相等时
                {
                        j++;k++;                                    
                        next = k;
                }
                else k = next;
        }
}
//说明：上述定义的next[]在某些情况下仍有缺陷，例如，设主串s为"aaabaaaab",模式串t为"aaaab"

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

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

～风介～ 发表于 2015-10-26 14:02:15

之前学过， 现在忘记光光了~~ {:7_140:}

淫令天下 发表于 2015-10-30 09:53:49

支持楼主！

qunianjinri 发表于 2015-11-5 15:58:20

本帖最后由 qunianjinri 于 2015-11-5 16:14 编辑

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

鱼C工作室.YCGZS 发表于 2015-11-24 17:14:30

感谢分享

孤心傲 发表于 2015-11-30 13:01:15

就是来顶 支持

斩月and剡月 发表于 2015-12-1 08:55:37

就是来顶 支持:lol:

磨牙耗子 发表于 2018-4-24 16:17:02

本帖最后由 磨牙耗子 于 2018-4-24 20:51 编辑

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

#include<stdio.h>      
                                               //为什么没有用strlen函数的有文件#include<string.h>也可以实现。
int main()
{
        char str[]="fishcshe.com",str2;
        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==str2)
                        {
                                count++;
                                if(count==n)
                                {
                                        blag=i;
                                        break;
                                }
                        }
                        else
                                break;
                }                       
        }
        if(blag>0)
       
                        printf("子串在主串第%d位存在\n",blag+1);
        else
                printf("子串不在主串中\n");
}

查看完整版本: 关于BF算法和KMP算法