精华内容
下载资源
问答
  • 拓展kmp)
    2017-10-27 20:36:19

                                                        拓展KMP算法

    对于某些题目,偶尔会出现KMP算法超时的情况,这个时候就要用到EKMP算法了

    EKMP主要求两个数组

    next数组和extend数组

    对于两个字符串,他们的next数组和extend数组为

    如给你一个T字符串,求s串在T中的位置

    T :  a  a  a  b  c  a
    ex:  2  4  1  0  0  1
    S :  a  a  b  c
    ne:  4  1 0  0

    明显可以看出,next数组的含义为  next[ i ]表示s串从第i个字符开始,与s串匹配的个数

    ex数组的含义是 ex[ i ]表示从T串第i个字符开始,与S串匹配的个数

    EKMP算法的核心思想:

    对于匹配过程中  如果s[0,5]和T[0,5]匹配成功了(表示字符串s和T从s[0],T[0]到S[5],T[5]都匹配成功)

    那么  s[1,5]和T[1,5]必定也匹配成功

    那么这部分在下次运用的时候就不必再进行匹配了

    关键就是如何利用这部分

    用a记录匹配成功的开始地方

    p记录匹配成功的结束地方(即最远匹配的距离)  

    p-a+1必定小于等于s串的长度

    next[i-a]表示T[i]往后匹配S串能匹配的长度

    下面代码

    #include<iostream>
    #include<string>
    #include<string.h>
    #include<stdio.h>
    using namespace std;
    char T[1000000],S[100000];
    /* 求解T中next[],注释参考GetExtend() */
    void GetNext(char *T, int next[])
    {
        int t_len = strlen(T);
        next[0] = t_len;
        int a;
        int p;
    
        for (int i = 1, j = -1; i < t_len; i++, j--)
        {
            if (j < 0 || i + next[i - a] >= p)
            {
                if (j < 0)
                    p = i, j = 0;
                    
                while (p < t_len&&T[p] == T[j])
                {
                    p++, j++;
                }
    
                next[i] = j;
                a = i;
            }
            else
                next[i] = next[i - a];
        }
    }
    
    /* 求解extend[] */
    void GetExtend(char *S, char *T, int extend[], int next[])
    {
        GetNext(T, next);  //得到next
        int a;
        int p;            //记录匹配成功的字符的最远位置p,及起始位置a
        int s_len = strlen(S);
        int t_len = strlen(T);
        for (int i = 0, j = -1; i < s_len; i++, j--)  //j即等于p与i的距离,其作用是判断i是否大于p(如果j<0,则i大于p)
        {
            if (j < 0 || i + next[i - a] >= p)  //j<0表示计算的字符已经到最远匹配位置了
            {
                //next[i-a]表示最多还能匹配几位,如果超过P了,那么不能取next[i-a]了
                if (j < 0)//如果i大于P
                {
                    p = i, j = 0;    //如果i大于p
                }
                while (p < s_len&&j < t_len&&S[p] == T[j])//如果可以匹配,继续匹配
                {
                    p++, j++;
                }
                extend[i] = j;
                a = i;
            }
            else
                extend[i] = next[i - a];
        }
    }
    
    int main()
    {
        int next[100] = { 0 };
        int extend[100] = { 0 };
        scanf("%s%s",T,S);
        GetExtend(S, T, extend, next);
        //打印next和extend
        cout << "next:    " << endl;
        for (int i = 0; i < strlen(T); i++)
            cout << next[i] << " ";
        cout << "\nextend:  " << endl;
        for (int i = 0; i < strlen(S); i++)
            cout << extend[i] << " ";
        cout << endl;
        return 0;
    }
    



















    更多相关内容
  • 拓展KMP

    2019-08-08 10:17:58
    摘自 拓展kmp算法总结 1、扩展KMP是什么?解决何种问题?与KMP算法的异同? 拓展kmp是对KMP算法的扩展,它解决如下问题: 定义母串S,和字串T,设S的长度为n,T的长度为m,求T与S的每一个后缀的最长公共前缀,也...

    摘自 拓展kmp算法总结


    1、扩展KMP是什么?解决何种问题?与KMP算法的异同?

    • 拓展kmp是对KMP算法的扩展,它解决如下问题:

      定义母串S,和字串T,设S的长度为n,T的长度为m,求T与S的每一个后缀的最长公共前缀,也就是说,设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀,要求出所有extend[i](0<=i<n)

    • 注意到,如果有一个位置extend[i]=m,则表示T在S中出现,而且是在位置i出现,这就是标准的KMP问题,所以说拓展kmp是对KMP算法的扩展,所以一般将它称为扩展KMP算法。

    • 图例:
      -S=”aaaabaa”T=”aaaaa”,首先,计算extend[0]时,需要进行5次匹配,直到发生失配。从而得知extend[0]=4
      这里写图片描述

      • 下面计算extend[1],在计算extend[1]时,是否还需要像计算extend[0]时从头开始匹配呢?答案是否定的,因为通过计算extend[0]=4,从而可以得出S[0,3]=T[0,3],进一步可以得到 S[1,3]=T[1,3],计算extend[1]时,事实上是从S[1]开始匹配。

    2、拓展kmp算法一般步骤

    • **1、**首先我们从左到右依次计算extend数组,在某一时刻,设extend[0...k]已经计算完毕,并且之前匹配过程中所达到的最远位置为P,所谓最远位置,严格来说就是i+extend[i]-1的最大值(0<=i<=k),并且设取这个最大值的位置为po,如在上一个例子中,计算extend[1]时,P=3,po=0。

    这里写图片描述

    • **2、**现在要计算extend[k+1],【注意啦!这里我们推的是k+1的公式,而在代码中是写的k的公式,会差一个1,不要搞错咯!】根据extend数组的定义,可以推断出S[po,P]=T[0,P-po],从而得到 S[k+1,P]=T[k-po+1,P-po],令len=next[k-po+1],(这里len也就是可以从头开始匹配上的字符长度),分两种情况讨论:

      • 2.1 第一种情况:k+len < P

        • 2.1.1
          也就是说从T字符串的k - po + 1位置推断出的从T的0开头可以匹配的长度len并没有超过现有P的大小,而po - p之间的字符是可以被匹配的这一事实我们已经检验过,所以可以确保从k+1 ~ k + len的字符,确实可以从T头开始匹配len的长度
      • **2.1.2 **图例

      • 2.1.3
        上图中,S[k+1,k+len]=T[0,len-1],然后S[k+len+1]一定不等于T[len],因为如果它们相等,则有S[k+1,k+len+1]=T[k+po+1,k+po+len+1]=T[0,len],那么next[k+po+1]=len+1,这和next数组的定义不符(next[i]表示T[i,m-1]和T的最长公共前缀长度),所以在这种情况下,不用进行任何匹配,就知道extend[k+1]=len

      • **2.2 ** 第二种情况:k+len>=P

        • 2.2.1
          也就是说从T字符串的k - po + 1位置推断出的从T的0开头可以匹配的长度len已经超过了现有P的大小,而po - p之间的字符是可以被匹配的这一事实我们已经检验过,但超过p的部分我们并没有匹配过,所以不能确保从k +1~ k + len的字符是否可以从T头开始匹配len的长度,只能说至少可以确定k+1 ~ p是匹配的,而p + 1 ~ k + len的部分还需要进一步比对 。
        • **2.2.2 **图例
        • 2.2.3
          上图中,S[p+1]之后的字符都是未知的,也就是还未进行过匹配的字符串,所以在这种情况下,就要从S[P+1]T[P-k+1]开始一一匹配,直到发生失配为止,当匹配完成后,如果得到的extend[k+1]+(k+1)大于P则要更新未知P和po。(得到的extend[k+1]+(k+1)至少都是p,要么就比p还大,所以在更新完extend之后,直接让p= extend即可)。
    • **3、**至此,拓展kmp算法的过程已经描述完成,事实上,计算next数组的过程和计算extend[i]的过程完全一样,将它看成是以T为母串,T为字串的特殊的拓展kmp算法匹配就可以了,计算过程中的next数组全是已经计算过的,所以按照上述介绍的算法计算next数组即可。

    3、时间复杂度分析

    通过上面的算法介绍可以知道,对于第一种情况,无需做任何匹配即可计算出extend[i],对于第二种情况,都是从未被匹配的位置开始匹配,匹配过的位置不再匹配,也就是说对于母串的每一个位置,都只匹配了一次,所以算法总体时间复杂度是O(n)的,同时为了计算辅助数组next[i]需要先对字串T进行一次拓展kmp算法处理,所以拓展kmp算法的总体复杂度为O(n+m)的。其中n为母串的长度,m为子串的长度。

    4、核心代码模板

    const int maxn = 100010; //字符串长度最大值
    int next[maxn], ex[maxn]; //ex数组即为extend数组
    //预处理计算next数组
    void GETNEXT(char *str)
    {
        int i = 0, j, po, len = strlen(str);
        next[0] = len; //初始化next[0],因为从0开头就可以匹配整个T,故为len   /*与EXKMP代码不同处:无这句话*/
        while(str[i] == str[i + 1] && i + 1 < len) //计算next[1]  /*与EXKMP代码不同处:比较s1和s2*/
            i++;
        next[1] = i;/*与EXKMP代码不同处:ex[0]=i*/
        po = 1; //初始化po的位置  /*与EXKMP代码不同处:po = 0*/
        for(i = 2; i < len; i++)/*与EXKMP代码不同处:i从1开始*/
        {
            if(next[i - po] + i < next[po] + po) //第一种情况,可以直接得到next[i]的值  /*与EXKMP代码不同处:next[i-po]+i<ex[po]+po*/
                next[i] = next[i - po];/*与EXKMP代码不同处:ex[i]=next[i-po];*/
            else//第二种情况,要继续匹配才能得到next[i]的值
            {
                j = next[po] + po - i;/*与EXKMP代码不同处:j=ex[po]+po-i;*/
                if(j < 0)j = 0; //如果i>po+next[po],则要从头开始匹配
                while(i + j < len && str[j] == str[j + i]) //计算next[i]  /*与EXKMP代码不同处:i+j<len&&j<l2&&s1[j+i]==s2[j]*/
                    j++;
                next[i] = j;/*与EXKMP代码不同处:ex[i]=j;*/
                po = i; //更新po的位置
            }
        }
    }
    //计算extend数组
    void EXKMP(char *s1, char *s2)
    {
        int i = 0, j, po, len = strlen(s1), l2 = strlen(s2);
        GETNEXT(s2);//计算子串的next数组
        while(s1[i] == s2[i] && i < l2 && i < len) //计算ex[0]
            i++;
        ex[0] = i;
        po = 0; //初始化po的位置
        for(i = 1; i < len; i++)
        {
            if(next[i - po] + i < ex[po] + po) //第一种情况,直接可以得到ex[i]的值
                ex[i] = next[i - po];
            else//第二种情况,要继续匹配才能得到ex[i]的值
            {
                j = ex[po] + po - i;
                if(j < 0)j = 0; //如果i>ex[po]+po则要从头开始匹配
                while(i + j < len && j < l2 && s1[j + i] == s2[j]) //计算ex[i]
                    j++;
                ex[i] = j;
                po = i; //更新po的位置
            }
        }
    }
    
    展开全文
  • 浅谈拓展kmp(z函数)

    2021-09-04 11:03:39
    拓展kmp函数(z函数)在竞赛中比较冷门,但是学习了z函数会提升对于manacher和kmp这一类的字符串处理算法的理解.它本身其实也是按照的kmp的思想. 扩展KMP求的是对于文本串S1的每一个后缀子串与模式串S2的最长公共前缀,...

    先贴一波kmpmanacher的博客,对于理解这个很有用:

    https://blog.csdn.net/qq_49593247/article/details/120077670?spm=1001.2014.3001.5501

    拓展kmp函数(z函数)在竞赛中比较冷门,但是学习了z函数会提升对于manacher和kmp这一类的字符串处理算法的理解.它本身其实也是按照的kmp的思想.

    扩展KMP求的是对于文本串S1的每一个后缀子串与模式串S2的最长公共前缀,类似于manacher算法,它也会存一个右端点在已经匹配过的点的最右端的点.它还存在一个next数组和extend数组,next数组含义类似于kmp的next数组,所存的数据是从模式串第i位开始和它的第一位匹配匹配,所匹配的最长前缀的长度.而extend数组则是存的文本串和模式串相匹配的该结果.

    例如:有文本串aaaabba和模式串aaaaa.

     为什么我们要预先处理一个next数组呢,类似于kmp算法,当在匹配过程中,模式串的前缀和文本串后缀所匹配的长度的值其实就等于模式串自己和自己匹配,因为匹配了此时两者是相等的,那么就可以在文本串与模式串匹配时直接用next来获取模式串长度为i时最长的公共前缀长度.

    然后就是匹配的思想了.

    我们会存一个两个字符串相等是能匹配的最长长度的起点p,并且用一个now值去记录该字符串的长度.所以一开始我们没有进行匹配,所以我们就要去求此时的起点和匹配的长度:

        int now=0;//此时没有进行匹配,长度就是0
        while(str1[now]==str[now]&&now<len1&&now<len)
            now++;//从0开始匹配,字符相匹配那么长度就增加    
        extend[0]=now;//文本串从0开始的后缀与模式串相匹配的长度
        int p=0;//记录起点

    储存之后,我们从1开始匹配,匹配时就会出现两种情况:

    1.i+nex[i-p]<p+extend[p]

    第一种情况从当前位置i开始(此时1到n-1的nex值和extend值已经算出来了).p是之前匹配的最右串的起点,p没有更新,所以i-p就是指此时文本串和模式串已经匹配的长度,因为此时文本串的p和模式串的头是对在一起的.所以i+nex[i-p]就是指模式串从i加上此时从i开始的模式串的后缀和模式串前缀匹配的最长前缀的长度(此时p到nex[p]以及全部是相等的了,可以看做是模式串的一部分)的位置.此时extend[i]的值就是此长度(i-p)的next值,也就是截取的模式串i开始的后缀和模式串前缀相等的这段的最长公共前缀的长度.

    if(i+nex[i-p]<p+extend[p])extend[i]=nex[i-p];

    2.i+nex[i-p]>=p+extend[p]

    当超过存的最长匹配串的右端时,因为右端没有进行匹配,说明此时i开始往后的这个匹配串会成为新的最右端匹配串,所以我们就暴力往后匹配,此处有一个类似于kmp的往后移动模式串的过程.将模式串的头对准i,然后因为之前的预处理,到p+extend[p]为止,两个串已经匹配好了,那么再往后面暴力匹配即可:

            else
            {
                now=p+extend[p]-i;
                now=max(now,0);//防止出现负数
                while(str[now+i]==str1[now]&&now+i<len&&now<len1)
                {
                    now++;
                }//包里匹配
                extend[i]=now;
                p=i;//更新
            }

     这就是拓展kmp的大致流程,接下来就整一个洛谷的模板题,把代码贴上去:

    https://www.luogu.com.cn/problem/P5410

    #include<iostream>
    #include<cstring>
    #define ll long long
    using namespace std;
    char str[20000007],str1[20000007];
    //str为文本串,str1是模式串
    ll nex[20000007],extend[20000007],len,len1;
    void getnex()//对模式串进行匹配
    {
        nex[0]=len1;
        int now=0;
        while(str1[now]==str1[now+1]&&now+1<len1)now++;
        nex[1]=now;
        int p=1;
        for(int i=2;i<len1;i++)
        {
            if(i+nex[i-p]<p+nex[p])nex[i]=nex[i-p];
            else
            {
                now=p+nex[p]-i;
                now=max(now,0);
                while(str1[now+i]==str1[now]&&now+i<len1)
                {
                    now++;
                }
                nex[i]=now;
                p=i;
            }
        }
        return ;
    }
    void getextend()//模式串与文本串匹配
    {
        getnex();
        int now=0;
        while(str1[now]==str[now]&&now<len1&&now<len)now++;
        extend[0]=now;
        int p=0;
        for(int i=1;i<len;i++)
        {
            if(i+nex[i-p]<p+extend[p])extend[i]=nex[i-p];
            else
            {
                now=p+extend[p]-i;
                now=max(now,0);
                while(str[now+i]==str1[now]&&now+i<len&&now<len1)
                {
                    now++;
                }
                extend[i]=now;
                p=i;
            }
        }
        return ;
    }
    int main()
    {
        scanf("%s%s",str,str1);
        len=strlen(str);
        len1=strlen(str1);
        ll z=0,p=0;
        getextend();
        for(int i=0;i<len1;i++)
        {
            z^=1ll*(i+1)*(nex[i]+1);
        }
        for(int i=0;i<len;i++)
        {
            p^=1ll*(i+1)*(extend[i]+1);
        }
        printf("%lld\n%lld\n",z,p);
        return 0;
    }

    其实拓展kmp思想也是从kmp而来,所以学好kmp很重要!

    展开全文
  • 拓展kmp算法总结

    2018-11-22 15:01:29
    拓展kmp是对KMP算法的扩展,它解决如下问题: 定义母串S,和字串T,设S的长度为n,T的长度为m,求T与S的每一个后缀的最长公共前缀,也就是说,设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀,要求出所有...

    https://blog.csdn.net/dyx404514/article/details/41831947


    拓展kmp是对KMP算法的扩展,它解决如下问题:

    定义母串S,和字串T,设S的长度为n,T的长度为m,求T与S的每一个后缀的最长公共前缀,也就是说,设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀,要求出所有extend[i](0<=i<n)。

    注意到,如果有一个位置extend[i]=m,则表示T在S中出现,而且是在位置i出现,这就是标准的KMP问题,所以说拓展kmp是对KMP算法的扩展,所以一般将它称为扩展KMP算法。

    下面举一个例子,S=”aaaabaa”,T=”aaaaa”,首先,计算extend[0]时,需要进行5次匹配,直到发生失配。

    从而得知extend[0]=4,下面计算extend[1],在计算extend[1]时,是否还需要像计算extend[0]时从头开始匹配呢?答案是否定的,因为通过计算extend[0]=4,从而可以得出S[0,3]=T[0,3],进一步可以得到 S[1,3]=T[1,3],计算extend[1]时,事实上是从S[1]开始匹配,设辅助数组next[i]表示T[i,m-1]和T的最长公共前缀长度。在这个例子中,next[1]=4,即T[0,3]=T[1,4],进一步得到T[1,3]=T[0,2],所以S[1,3]=T[0,2],所以在计算extend[1]时,通过extend[0]的计算,已经知道S[1,3]=T[0,2],所以前面3个字符已经不需要匹配,直接匹配S[4]和T[3]即可,这时一次就发生失配,所以extend[1]=3。这个例子很有代表性,有兴趣的读者可以继续计算完剩下的extend数组。

    1. 拓展kmp算法一般步骤

    通过上面的例子,事实上已经体现了拓展kmp算法的思想,下面来描述拓展kmp算法的一般步骤。

    首先我们从左到右依次计算extend数组,在某一时刻,设extend[0...k]已经计算完毕,并且之前匹配过程中所达到的最远位置为P,所谓最远位置,严格来说就是i+extend[i]-1的最大值(0<=i<=k),并且设取这个最大值的位置为po,如在上一个例子中,计算extend[1]时,P=3,po=0。

       

    现在要计算extend[k+1],根据extend数组的定义,可以推断出S[po,P]=T[0,P-po],从而得到 S[k+1,P]=T[k-po+1,P-po],令len=next[k-po+1],(回忆下next数组的定义),分两种情况讨论:

    第一种情况:k+len<P

    如下图所示:

      

    上图中,S[k+1,k+len]=T[0,len-1],然后S[k+len+1]一定不等于T[len],因为如果它们相等,则有S[k+1,k+len+1]=T[k+po+1,k+po+len+1]=T[0,len],那么next[k+po+1]=len+1,这和next数组的定义不符(next[i]表示T[i,m-1]和T的最长公共前缀长度),所以在这种情况下,不用进行任何匹配,就知道extend[k+1]=len。

    第二种情况: k+len>=P

    如下图:

     

    上图中,S[p+1]之后的字符都是未知的,也就是还未进行过匹配的字符串,所以在这种情况下,就要从S[P+1]和T[P-k+1]开始一一匹配,直到发生失配为止,当匹配完成后,如果得到的extend[k+1]+(k+1)大于P则要更新未知P和po。

    至此,拓展kmp算法的过程已经描述完成,细心地读者可能会发现,next数组是如何计算还没有进行说明,事实上,计算next数组的过程和计算extend[i]的过程完全一样,将它看成是以T为母串,T为字串的特殊的拓展kmp算法匹配就可以了,计算过程中的next数组全是已经计算过的,所以按照上述介绍的算法计算next数组即可,这里不再赘述。

    2. 时间复杂度分析

    下面来分析一下算法的时间复杂度,通过上面的算法介绍可以知道,对于第一种情况,无需做任何匹配即可计算出extend[i],对于第二种情况,都是从未被匹配的位置开始匹配,匹配过的位置不再匹配,也就是说对于母串的每一个位置,都只匹配了一次,所以算法总体时间复杂度是O(n)的,同时为了计算辅助数组next[i]需要先对字串T进行一次拓展kmp算法处理,所以拓展kmp算法的总体复杂度为O(n+m)的。其中n为母串的长度,m为子串的长度。

    下面是拓展kmp算法的关键部分代码实现。

    const int maxn=100010;   //字符串长度最大值
    int next[maxn],ex[maxn]; //ex数组即为extend数组
    //预处理计算next数组
    void GETNEXT(char *str)
    {
        int i=0,j,po,len=strlen(str);
        next[0]=len;//初始化next[0]
        while(str[i]==str[i+1]&&i+1<len)//计算next[1]
        i++;
        next[1]=i;
        po=1;//初始化po的位置
        for(i=2;i<len;i++)
        {
            if(next[i-po]+i<next[po]+po)//第一种情况,可以直接得到next[i]的值
            next[i]=next[i-po];
            else//第二种情况,要继续匹配才能得到next[i]的值
            {
                j=next[po]+po-i;
                if(j<0)j=0;//如果i>po+next[po],则要从头开始匹配
                while(i+j<len&&str[j]==str[j+i])//计算next[i]
                j++;
                next[i]=j;
                po=i;//更新po的位置
            }
        }
    }
    //计算extend数组
    void EXKMP(char *s1,char *s2)
    {
        int i=0,j,po,len=strlen(s1),l2=strlen(s2);
        GETNEXT(s2);//计算子串的next数组
        while(s1[i]==s2[i]&&i<l2&&i<len)//计算ex[0]
        i++;
        ex[0]=i;
        po=0;//初始化po的位置
        for(i=1;i<len;i++)
        {
            if(next[i-po]+i<ex[po]+po)//第一种情况,直接可以得到ex[i]的值
            ex[i]=next[i-po];
            else//第二种情况,要继续匹配才能得到ex[i]的值
            {
                j=ex[po]+po-i;
                if(j<0)j=0;//如果i>ex[po]+po则要从头开始匹配
                while(i+j<len&&j<l2&&s1[j+i]==s2[j])//计算ex[i]
                j++;
                ex[i]=j;
                po=i;//更新po的位置
            }
        }
    }

     

    展开全文
  • 拓展KMP算法详解

    千次阅读 2017-08-22 09:13:44
    下面说一说具体如何实现拓展kmp算法 首先我们要引入两个新的变量,p,p0。表示p从p0开始最长的匹配位置(如果感到模糊请继续看下去)。与manacher类似,我们需要维护这个最长长度。下面通过几个图来讲解一下。 ...
  • KMP&拓展KMP

    2018-09-27 11:38:00
    KMP算法 说明 KMP算法是一种比较高效的字符串匹配算法,可以在线性时间内求出一个串在另一个串的所有匹配位置。 解析 详解KMP 设模板串是 \(pattern\) 令 \(next[i] = max\{k|pattern[0...k-1]=pattern[i-k+1...i]\}...
  • 拓展KMP】 【前言】 著名的模式匹配算法有BF算法和KMP算法,本文章主要着重讲KMP算法及其拓展。 【BF算法】 BF(Brute-Force)算法,是最简单直观的模式匹配算法。 看下图,上边的是主串a,下边的是模式串b。...
  • 拓展kmp

    2018-12-18 15:10:12
    算法总结第二弹,上次总结了下kmp,这次就来拓展kmp吧。 拓展kmp是对KMP算法的扩展,它解决如下问题: 定义母串S,和字串T,设S的长度为n,T的长度为m,求T与S的每一个后缀的最长公共前缀,也就是说,设extend数组,...
  • 拓展KMP分析

    2018-06-07 00:49:00
    拓展kmp是对KMP算法的扩展,它解决如下问题:定义母串S,和字串T,设S的长度为n,T的长度为m,求T与S的每一个后缀的最长公共前缀,也就是说,设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀,要求出所有...
  • 拓展KMP

    2019-08-09 16:11:05
    #include<stdio.h> #include<string.h> int next[100010],ex[100010]; void getnext(char *str) { int i=0,j,po,len=strlen(str); next[0]=len; while(str[i]==str[i+1]&......
  • KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris 和 V.R.Pratt 同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串...
  • KMP算法 KMP算法是一种线性时间复杂度的字符串匹配算法,它是对BF(Brute-Force,最基本的字符串匹配算法)的改进。对于给定的原始串S和模式串T,需要从字符串S中找到字符串T出现的位置的索引。KMP算法由D.E.Knuth与V...
  • 拓展 KMP 学习

    2018-02-14 19:16:32
    初识扩展 KMP , 看了挺久的。可以参考这篇博客 和 第二篇给定两个字符串 S , T (序列),求( S 的所有后缀 )和 T 的最长前缀。例如 S 是 abcde求 abcde 和 T 的最长前缀求 bcde 和 T 的最长前缀求 ...
  • 拓展Kmp模板

    2019-03-17 16:25:37
    bin神的模板~~~ //nt[i]:x[i...m-1]与x[0...m-1]的最长公共前缀 //extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀 void pre_eKmp(char s[],int nt[]) { int m = strlen(s); nt[0] = m;...
  • KMP&拓展KMP 复习笔记

    2022-08-07 18:41:05
    蒟蒻君の复习笔记之字符串——KMP&exKMP
  • 这里用拓展KMP实现 时间是1439 #include #include #include #include #include using namespace std; const int MAX_N = 1000024; int str[MAX_N],T[MAX_N]; int Next[MAX_N],ex[MAX_N]; int n,m; void getnext...
  • 拓展kmp算法

    2018-10-21 15:04:37
    拓展kmp是对KMP算法的扩展,它解决如下问题: 定义母串S,和字串T,设S的长度为n,T的长度为m,求T与S的每一个后缀的最长公共前缀,也就是说,设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀,要求出所有...
  • 分开后,如果那部分是回文的话,那么价值就是该部分字符的价值和,如果不是回文,价值为0,问分开后的最大价值和解题思路:可以用KMP做也可以用拓展KMP做KMP做的话,假设原字符串是s1,然后将字符串倒转变成s2,先求...
  • 拓展kmp板题 emm。。。我比较懒 最后一个字母进了vector两个1 不想改了。。。就加了个去重。。。 哈哈 #include <iostream> #include <cstdio> #include <sstream> #include <cstring&...
  • 几篇关于拓展KMP的论文,字符串题目的必备工具

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,399
精华内容 959
关键字:

拓展kmp)