基于的BF算法算法设计方案设计的设计思路和应用

  BF算法

  算法思路：

  比较简单，定义i，j分别指向主字符串和字符串的头部），依次向后比较，如果比较失败，则主字符串和字符串都需要回溯（i =比较轮数的位置+1，j返回0位置）

  

  元素相同，所以 i 和 j 向后移动一位

  

  元素不同，我回到第二个位置。j 变为 0

  

  元素还是不一样，i退到第三位

  

  

  

  结束

  

   #include

    #include
    bool BF(char a[],char b[]){
        int index1 = 0;//指向a的头部 
        int index2 = 0;//指向b的头部 
        for(int i = 0;i -1 && a[k + 1] != a[q])
            {
                k = next[k];//往前回溯
            }
            if (a[k + 1] == a[q])//如果相同，k++
            {
                k = k + 1;
            }
            next[q] = k;
        }
    }
    bool KMP(char a[],char b[]){
        int next[strlen(a)];
        getNext(a,next);
        int i = 0;
        int j = 0;
        int len1 = strlen(a);
        int len2 = strlen(b);
        while(i -1 && a[k + 1] != a[q])
            {
                k = next[k];//往前回溯
            }
            if (a[k + 1] == a[q])//如果相同，k++
            {
                k = k + 1;
            }
            next[q] = k;
        }

  循环查找下一个数组，q是最后一个数字，k是前缀公共部分的最后一个（last found）的下一个，如果这个数字等于a[q]，那么公共部分可以加1（因为原来前缀和后缀的公共部分的长度是K，现在后缀中多了一个元素来判断公共部分之外的第一个元素是否与这个元素重合） ，否则我们将回溯，直到找到一个新的（较小的）公共部分。部分

  文章来源:https://www.csdn.net/tags/MtTaAg4sNzIxNDczLWJsb2cO0O0O.html