关于BF算法和KMP算法

零度非安全

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

1. //Brute-Force算法
   
2. int index(SqString s,SqString t)                    //目标串s，模式串t
   
3. {
   
4.         int i = 0,j = 0;                                                                //指针下标i标志s串，指针下标j标志t串
   
5.         while(i < s.length && j < t.length)             //当各自指针下标小于各自的串的长度时，则执行该循环体
   
6.         {
   
7.                 if(s.data[i] == t.data[j])                  //如相等则继续匹配下一个字符
   
8.                 {
   
9.                         i++;                                    //主串和子串依次匹配下一个字符
   
10.                         j++;
    
11.                 }
    
12.                 else                                        //如果不相等主串、子串指针回溯重新开始下一次匹配
    
13.                 {
    
14.                         i = i - j + 1;                          //主串从下一个位置开始匹配
    
15.                         j = 0;                                  //子串从头开始匹配
    
16.                 }
    
17.         }
    
18.         if(j >= t.length)
    
19.                 return(i - t.length);                       //返回匹配的第一个字符的下标
    
20.         else
    
21.                 return(-1);                                 //模式匹配不成，返回-1
    
22. }
    
23. //总结：这个算法简单，易于理解，但效率不高，主要原因是：主串指针i在若干个字符序列比较相等后，若有一个字符比较不相等，仍需回溯(即i = i - j + 1)
    
24. //该算法在最好的情况下的时间复杂度为O(m)，即主串的前m个字符等于模式串的m个字符。在最坏的情况下的时间复杂度为O(nm)
    
25. 
    
26. //KMP算法
    
27. int KMPIndex(SqString s,SqString t)                        
    
28. {
    
29.         int next[MaxSize],i = 0,j = 0;
    
30.         GetNext(t,next);
    
31.         while(i < s.length && j < t.length)
    
32.         {
    
33.                 if(j == -1 || s.data[i] == t.data[j])
    
34.                 {
    
35.                         i++;
    
36.                         j++;                                          //i,j各增1
    
37.                 }
    
38.                 else j = next[j];                                 //i不变，j后退
    
39.         }
    
40.         if(j >= t.length)
    
41.                 return(i - t.length);
    
42.         else
    
43.                 return(-1);
    
44. }
    
45. 
    
46. 
    
47. //求next[]的值
    
48. void GetNext(SqString t.int next[])                         //对模式串t，求next[]值
    
49. {
    
50.         int j,k;
    
51.         j = 0;k = -1;next[0] = -1;
    
52.         while(j < t.length - 1)
    
53.         {
    
54.                 if(k == -1 || t.data[j] == t.data[k])              //k为-1或比较的字符相等时
    
55.                 {
    
56.                         j++;k++;                                    
    
57.                         next[j] = k;
    
58.                 }
    
59.                 else k = next[k];
    
60.         }
    
61. }
    
62. //说明：上述定义的next[]在某些情况下仍有缺陷，例如，设主串s为"aaabaaaab",模式串t为"aaaab"
    
63. 
    
64. //修正后的求nextval数组的算法如下：
    
65. void GetNextval(SqString t,int nextval[])
    
66. {
    
67.         int j = 0,k = -1;
    
68.         nextval[0] = -1;
    
69.         while(j < t.length)
    
70.         {
    
71.                 if(k == -1 || t.data[j] == t.data[k])
    
72.                 {
    
73.                         if(t.data[j]!=t.data[k])
    
74.                                 nextval[j] = k;
    
75.                         else
    
76.                                 nextval[j] = nextval[k];
    
77.                 }
    
78.                 else
    
79.                         k = nextval[k];
    
80.         }
    
81. }
    
82. 
    
83. //修正后的KMP算法如下：
    
84. int KMPIndex(SqString s,SqString t)
    
85. {
    
86.         int nextval[MaxSize],i = 0,j = 0;
    
87.         GetNextval(t,nextval);
    
88.         while(i < s.length && j < t.length)
    
89.         {
    
90.                 if(j == -1 || s.data[i] == t.data[j])
    
91.                 {
    
92.                         i++;
    
93.                         j++;
    
94.                 }
    
95.                 else
    
96.                         j = nextval[j];
    
97.         }
    
98.         if(j >= t.length)
    
99.                 return(i - t.length);
    
100.         else
     
101.                 return(-1);
     
102. }
     
103. 
     

复制代码

～风介～

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

淫令天下

支持楼主！

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");
}