欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

串(2)

程序员文章站 2022-05-02 11:42:44
...

算法目的 :确定子串在主串中第一次出现的位置 两种算法: BF,KMP(重点掌握) 一:BF算法 1.特点:主串的指针需回溯,速度慢; 2.算法思想: 当主串T(长为m)和子串S(长为n)的比较字符不相等时,主串的指针i需要指向之前开始比较的位置的后面一个字符(相应的子串的

算法目的:确定子串在主串中第一次出现的位置

两种算法:BF,KMP(重点掌握)

一:BF算法

1.特点:主串的指针需回溯,速度慢;

2.算法思想:

当主串T(长为m)和子串S(长为n)的比较字符不相等时,主串的指针i需要指向之前开始比较的位置的后面一个字符(相应的子串的指针j需要重新指到1),,这样依次拿子串T和主串的一个连续子字符串比较知道两个串相等为止。

int Index_BF(SString S, SString T, int pos)//pos为从哪个位置开始找,设两个字符串下标都是从1开始
{
   if(posT.length)
      return i-T.length; //或者i-j+1
   else
      return 0;//没找到
}
3.时间复杂度分析:

最好情况:只需比较一次,即比较子串的长度的次数n=O(n);

最差情况:每次比较时都发现子串的最后一个字符和主串不相等,故需要比较(m-n)*n+n=(m-n+1)*n=O(m*n)次

一般情况:O(m+n);//要从最好到最坏情况统计总的比较次数,然后取平均。


二.KMP算法(详细推理过程本人依然不是很理解,不过以下的掌握了就大致能意会了):

1.特点:比较时,主串的指针i不需要回溯,只需把子串向右滑动若干距离

2.思想:尽量利用已经部分匹配的结果信息,尽量让i不要回溯,加快模式串的滑动速度。

3.求k=next[j]:

1).j表示正在比较的子串和主串的失配的位置,k=next[j]表示下一次主串应该和子串比较的时候子串的字符指针所在的位置;

2).next[j]函数象征着模式T中最大相同前缀子串和后缀子串(真子串)的长度。
可见,模式中相似部分越多,则next[j]函数越大,它既表示模式T字符之间的相关度越高,也表示j位置以前与主串部分匹配的字符数越多。
即:next[j]越大,模式串向右滑动得越远,与主串进行比较的次数越少,时间复杂度就越低(时间效率)。

3).求法:(推导见>原文)

串(2)

4代码实现(求next[j]函数):

void get_next(SString T, int  &next[ ] )
{ 
    //求模式串T的next函数值并存入数组next[ ]。
    i=1;  next[1]=0; j=0;
    while(i
5.完整KMP实现:

Int Index_KMP(SString S, SString T, int pos)//与BF算法比较(类似)
{   
   if(posT.length)
           return i-T.length; //子串结束,说明匹配成功 else 
   return 0;//没找到}//Index_KMP



6.讨论现在的next[j]函数是否完善:

1).我们假设主串T为 a a a b a a a a b,

子串S为 a a a a b;

求得S的next[j]=0,1,2,3,4;

我们可以自己模拟上面的完整的KMP算法,发现当主串的指针i和子串的指针j都指向4时,此时失配,j=next[4]=3,又发现失配,j=next[3]=2,又失配.....依次j指向0,然后i=5,j=1,才匹配,在此过程中我们可以发现KMP算法并没有起到作用,那是因为子串存在很多相同的前缀,导致主串不匹配的字符与子串比较了多次,即next[j]的函数不完善!!!!

2).完善的next[j]算法:

void get_nextval(SString T, int  &nextval[ ] )
{
    //next函数修正值存入数组nextval
    i=1;  nextval[1]=0; j=0;
    while(i7.时间复杂度分析:

由于指针i无须回溯,比较次数仅为m,即使加上计算next[j]时所用的比较次数n,比较总次数也仅为m+n=O(m+n),大大快于BF算法。