BF算法 + KMP算法

准备：

字符串比大小：比的就是字符串里每个字符的ASCII码的大小。（其实这样的比较没有多大的意义，我们关心的是字符串是否相等，即匹配等）

字符串的存储结构：同线性表（顺序存储+链式存储）

　　顺序存储结构是一组地址连续的存储单元来存储字符串中的字符序列；按照预定义的大小，为每个定义的字符串变量分配一个固定长度的存储区，一般用定长数组来定义。——空间分配不灵活，但是字符串一般都是连在一起表述的，”断章取义“的情况并不多，所以习惯上我们还是会直接定义一个足够长度的存储区来存储。

　　链式存储结构

BF算法：

　　BoyFriend 、Brute Force

　　朴素的模式匹配算法，其核心思想是：

　　——有两个字符串S和T，长度分别为N和M。首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则T向右移动一个字符位置，与S[2]进行比较，而后再依次进行比较。

　　——该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。____效率低下。

(注：在这里S为主串，T为子串，这种子串的定位操作通常称作串的模式匹配)

　　存在回溯，需要重头来过，效率低下。

KMP算法：

　　克努特-莫里斯-普拉特算法，大大的避免重复遍历的情况(避免不必要的回溯)

　　问题由模式匹配串（子串）决定，不是由目标串决定。

　　给模式匹配串添加个k数组(即next数组)，这是一个”智能“的数组，因为它指导着模式匹配串下一步该用第几号元素进行匹配。

　　　　——k数组元素：k[1]=0，k[2]=1，然后从不匹配元素位置开始往前查看，探讨其前缀与后缀相同元素个数，k[i]即相同元素个数+1。

(解读next数组：当模式匹配串T失配的时候，next数组对应的元素指导应该用T串的哪个元素进行下一轮的匹配)

(注：模式匹配串和目标串的下标都是从1开始，0下标存储串的长度)

next数组获取示例演示：

next数组获取代码展示：

 //i(后缀)

 //j(前缀)

 void get_next(String T, int *next)

 {

     j = ;

     i = ;

     next[] = ;

     while( i < T[])

     {

         if(0 == j || T[i] == T[j])

         {

             i++;

             j++;

             next[i] = j;

         }

         else

         {

             j = next[j];//j回溯

         }

     }

     //因为前缀是固定的，后缀是相对的。

 }

next数组获取优化：

优化next数组代码如下：

 //优化

 //i(后缀)

 //j(前缀)

 void get_next(String T, int *next)

 {

     j = ;

     i = ;

     next[] = ;

     while( i < T[])

     {

         if(j ==  || T[i] == T[j])

         {

             i++;

             j++;

             if(T[i] != T[j])//判断

16             {

17                 next[i] = j;

18             }

19             else

20             {

21                 next[i] = next[j];

22             }

         }

         else

         {

             j = next[j];//j回溯

         }

     }

     //因为前缀是固定的，后缀是相对的。

 }

最后KMP.c

 //若存在，返回子串T在主串S第pos个字符之后的位置

 //若不存在返回0

 int Index_KMP(Stirng S, Stirng T, int pos)

 {

     int i = pos;

     int j = ;

     int next[];

     get_next(T, next);

     while(i <= S[] && j <= T[])

     {

         if( == j || S[i] == T[j])

         {

             i++;

             j++;

         }

         else

         {

             j = next[j];

         }

     }

     if(j > T[])

     {

         return i - T[];

     }

     else

     {

         return ;

     }

 }

巴特西

BF算法 + KMP算法

BF算法：

KMP算法：

最新文章

热门文章