扩展kmp_扩展kmp算法 - CSDN
精华内容
参与话题
  • 1. 扩展KMP问题:求字符串S的所有后缀和字符串T的最长公共前缀。 扩展KMP可以用来解决很多字符串问题,如求一个字符串的最长回文子串和最长重复子串。2. 拓展KMP的next[]数组怎么计算?在解上面这个问题前我们要先...

    1. 扩展KMP问题:

    求字符串S的所有后缀和字符串T的最长公共前缀。

    扩展KMP可以用来解决很多字符串问题,如求一个字符串的最长回文子串和最长重复子串。

    2. 拓展KMP的next[]数组怎么计算?

    在解上面这个问题前我们要先解决一个类似的问题:
    字符串s所有后缀字符串s本身的最长公共前缀;
    我们用next[]数组保存这些值;

    现在我们假设要求next[x],并且next[i](0<i<x)的值都已经求出;
    我们设 p=k+next[k]1k 是使 p 最大的 i(0<i<x)

    如图所示:
    这里写图片描述

    现在整理一下问题:

    已知:s[k..p]=s[0..next[k]1],求s[x..n1]s[0..n1]的最长公共前缀;

    解:
    s[k..p] =s[0..next[k]1] 得:
    s[x..p] = s[xk..next[k]1] …………………….(1) 这个是显然的

    并设 L1=px+1
    因为 xk<x,所以 L2=next[xk]是已知的,得:
    s[0..L21]=s[xk...xk+L21] …………………….(2)

    通过等式(1),(2)可以推出s[0..k1]=s[x..k2]

    L1L2时,如下图所示:
    这里写图片描述

    表示s[0..L11]=s[x..x+L11],但不能确定蓝色部分是否相等,所以需要继续比下去。

    L1>L2时,如下图所示:
    这里写图片描述

    表示s[0..L21]=s[x..x+L21]
    而且因为L2=next[xk],使得s[L2]s[x+L2]
    所以next[x]=L2

    证明:
    假设s[L2]=s[x+L2]
    又因为s[x+L2]==s[xk+L2]…………由(1)推出
    所以s[L2]=s[xk+L2]
    所以next[xk]=L2+1next[xk]=L2矛盾

    next[]数组的代码如下:

    void getNext(char *s, int next[]) {
        int lenS = strlen(s);
    
        next[0] = lenS;
        int p = 0;
        while (p+1 < lenS && s[p] == s[p+1]) p++;
    
        next[1] = p;
        int k = 1, L;
        for (int i = 2; i < lenS; i++) {
            p = k + next[k] - 1, L = next[i-k];
            if (i + L <= p)
                next[i] = L;
            else {
                int j = max(p-i+1, 0);
                while (i + j < lenS && s[i+j] == s[j]) j++;
                next[i] = j, k = i;
            } 
        }
    }

    3. 如何计算extend[]数组的值

    回到原来的问题
    此时已经求出next[],我们用extend[]保存字符串S的所有后缀和字符串T的最长公共前缀的值

    求解extend[]数组的方法 和 求解next[]数组的方法类似,重复上面的过程:

    假设要求extend[x],并且extend[i](0<i<x)的值都已经求出;
    我们设p=k+extend[k]1, k是使p最大的 i(0<i<x)

    如图所示:
    这里写图片描述

    整理一下问题:

    已知:s[k..p]=T[0..extend[k]1],求s[x..n1]T[0..m1]的最长公共前缀;

    解:
    s[k..p] =T[0..extend[k]1] 得:
    s[x..p] = T[xk..extend[k]1] …………………….(1)

    并设 L1=px+1
    因为 xk<x,所以 L2=next[xk]是已知的,得:
    T[0..L21]=T[xk...xk+L21] …………………….(2)

    通过等式(1),(2)可以推出T[0..k1]=s[x..k2]

    L1L2时,如下图所示:
    这里写图片描述

    表示T[0..L11]=s[x..x+L11],但不能确定蓝色部分是否相等,所以需要继续比下去。

    L1>L2时,如下图所示:
    这里写图片描述

    表示T[0..L21]=s[x..x+L21]
    而且因为L2=extend[xk],使得T[L2]s[x+L2]
    所以extend[x]=L2

    证明:
    假设T[L2]=s[x+L2]
    又因为s[x+L2]=T[xk+L2]…………由(1)推出
    所以T[L2]==s[xk+L2]
    所以extend[xk]=L2+1extend[xk]=L2矛盾

    extend[]数组的代码如下:

    void getExtend(char *s, char *T, int extend[], int next[]) {
        int lenS = strlen(s) ,lenT = strlen(T);
        getNext(s,next);
    
        int p = 0;
        while(p < lenS && s[p] == T[p]) p++;
    
        extend[0] = p;
        int k = 0, L;
        for(int i = 1; i < lenS; i++) {
            p = k + extend[k] - 1, L = next[i - k];
            if(i + L <= p)
                extend[i] = L;
            else {
                int j = max(p-i+1, 0);
                while (i + j < lenS && s[i + j] == T[j]) j++;
                extend[i] = j; k = i;
            } 
        }
    }

    4. 时间复杂度分析:

    对于s串,计算next[]数组的时间是O(n),计算extend[]数组的时间是O(m)的,总算法复杂度是O(n+m);

    此博文转自:http://www.cnblogs.com/Rlemon/archive/2013/06/26/3157574.html

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

    万次阅读 多人点赞 2014-12-09 22:11:09
    拓展kmp算法是对KMP算法的扩展,它解决如下问题: 定义母串S,和字串T,设S的长度为n,T的长度为m,求T与S的每一个后缀的最长公共前缀,也就是说,设extend数组,extend[i]表示T与S[i,n-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]开始匹配,设辅助数组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的详细理解

    万次阅读 2018-05-22 16:37:02
    扩展KMP的详细理解扩展KMP求的是对于原串S1的每一个后缀子串与模式串S2的最长公共前缀。它有一个next[]数组和一个extend[]数组。next[i]表示为模式串S2中以i为起点的后缀字符串和模式串S2的最长公共前缀长度.其中,...

    扩展KMP的详细理解

    扩展KMP求的是对于原串S1的每一个后缀子串与模式串S2的最长公共前缀。它有一个next[]数组和一个extend[]数组。

    next[i]表示为模式串S2中以i为起点的后缀字符串和模式串S2的最长公共前缀长度.

    其中,next[0]=l2;

    next[i]=max{ k|i<=i+k-1<l2 &&S2.substring(i,i+k-1) == S2.substring(0,k-1) }

    其中str.substring(i, j)表示str从位置i到位置j的子串,如果i>j则,substring为空。

    extend[i]表示为以字符串S1中以i为起点的后缀字符串和模式串S2的最长公共前缀长度.

    下面我们先以一组样例来理解扩展KMP的过程


    (1) 第一步,我们先对原串S1和模式串S2进行逐一匹配,直到发生不配对的情况。我们可以看到,S1[0]=S2[0],S1[1]=S2[1],S1[2]=S2[2],S1[3] ≠S2[3],此时匹配失败,第一步结束,我们得到S1[0,2]=S2[0,2],即extend[0]=3;

    (2) Extend[0]的计算如第一步所示,那么extend[1]的计算是否也要从原串S1的1位置,模式串的0位置开始进行逐一匹配呢?扩展KMP优化的便是这个过程。从extend[0]=3的结果中,我们可以知道,S1[0,2]=S2[0,2],那么S1[1.2]=S2[1,2]。因为next[1]=4,所以S2[1,4]=S2[0,3],即S2[1,2]=S[0,1],可以得出S1[1,2]=S2[1,2]=S2[0,1],然后我们继续匹配,S1[3] ≠S2[3],匹配失败,extend[1]=2;

    (3) 因为extend[1]=2,则S1[1,2]=S2[0,1],所以S1[2,2]=S2[0,0],因为next[0]=5,所以S1[0,5]=S2[0,5],所以S2[0,0]=S2[0,0],又回到S1[2,2]=S2[0,0],继续匹配下一位,因为S1[3] ≠S2[1],所以下一位匹配失败,extend[2]=1;

    (4) 到计算原串S1的3号位置(在之前的步骤中能匹配到的最远的位置+1,即发生匹配失败的位置),这种情况下,我们会回到步骤(1)的方式,从原串S1的3号位置开始和模式串的0号位置开始,进行逐一匹配,直到匹配失败,此时的extend[]值即为它的匹配长度。因为S1[3] ≠S2[0],匹配失败,匹配长度为0,即extend[3]=0;

    (5) 计算S1的4号位置extend[]。由于原串S1的4号位置也是未匹配过的,我们也是回到步骤(1)的方式,从原串S1的4号位置开始和模式串S2的0号位置开始进行逐一匹配,可以看到,S1[4]=S2[0],S1[5]=S2[1],S1[6]=S2[2],S1[7]=S2[3],S1[8]=S2[4],S1[9] ≠S2[5],此时原串S1的9号位置发生匹配失败,最多能匹配到原串S1的8号位置,即S1[4,8]=S2[0,4],匹配长度为5,即extend[4]=5;

    (6) 计算S1的5号位置extend[].由于原串S1的5号位置是匹配过的(在步骤(5)中匹配了),我们从extend[4]=5得出,S1[4,8]=S2[0,4],即S1[5,8]=S2[1,4],和步骤(2)的计算方式类似,我们从next[1]=4可知,S2[0,3]=S2[1,4],即S1[5,8]=S2[0,3],然后我们继续匹配原串S1的9号位置和S2的4号位置,S1[9]=S2[4],继续匹配,S1[10]=S2[5],此时原串S1的所有字符皆匹配完毕,皆大欢喜,则S1[5,10]=S2[0,5],extend[5]=6;

    (7) 从原串S1的6号位置到10号位置的extend[]的计算,与原串S1的1号位置到3号位置的计算基本相同。S1[6,10]=S2[1,5],因为next[1]=4,所以S2[1,4]=S[0,3],所以S1[6,9]=S2[0,3],此时不在需要判断匹配下一位的字符了,直接extend[6]=4;(具体原因在后面的分析总结中有说明)

    (8) S1[7,10]=S2[2,5],因为next[3]=2,所以S2[3,4]=S2[0,1],所以S1[8,9]=S2[0,1],匹配长度为2,即extend[7]=3;

    (9) S1[8,10]=S2[3,5],因为next[3]=2,所以S2[3,4]=S2[0,1],所以S1[8,9]=S2[0,1],匹配长度为2,即extend[8]=2;

    (10) S1[9,10]=S2[4,5],因为next[4]=1,所以S2[4,5]=S2[0,0],所以S1[9,9]=S2[0,0],匹配长度为1,即extend[9]=1;

    (11) S1[10,10]=S2[5,5],因为next[5]=0,所以匹配长度为0,即extend[10]=0;

    至此,所有的匹配已经结束,相信,如果你仔细的看了上述的例子,已经对扩展KMP有了一定的了解了,它的计算过程中,主要是步骤一和步骤二的计算过程。下面我们对这两个过程归纳一下:

     

    我们先定义,从0~k的计算过程中,我们已经计算出它们的extend[]值了和在匹配的过程中从Po开始匹配能匹配到的最远位置P,即Po+extend[Po]-1=P;

    步骤一:当前需要计算的extend[k+1],原串S1中k+1号位置还未进行过匹配,则从原串S1的k+1号位置和模式串S2的0号位置开始进行逐一匹配,直到匹配失败,则extend[k+1]=匹配长度,此外,还要相应的更新Po值和最远匹配位置P.

    步骤二:当前需要计算的extend[k+1],原串S1中k+1号位置已经进行过匹配。首先,我们从Po+extend[Po]-1=P中,可以得知S1[Po,P]=S2[0,P-Po],所以S1[k+1,P]=S2[k+1-Po,P-Po],令len=next[k+1-Po]

    (1) 当(k+1)+len-1=k+len<P时,即一下情况:

     

    我们可以得出,len=next[k+1-Po],S2[0,len-1]=S2[k+1-Po,k+Po+len],所以S1[k+1,k+len]=S2[k+1-Po,k+Po+len]=S2[0,len-1],即extend[k+1]=len;

    那么会不会出现S1[k+len+1]=S2[len]的情况呢?答案是否定的

    假如S1[k+len+1]=S2[len],则S1[k+1,k+len+1]=S2[0,len]

    因为k+len<P,所以k+len+1<=P

    所以S1[k+1,k+len+1]=S2[k+1-Po,k+Po+len+1]=S2[0,len]

    此时,next[k+1-Po]=len+1与原假设不符合,所以此时S1[k+len+1]≠S2[len],不需要再次判断。

    (2)当(k+1)+len-1=k+len>=P时,即一下情况:

     

    我们可以看出,由S1[Po,P]=S2[0,P-Po]可得出S1[k+1,P]=S2[k+1-Po,P-po],len=next[k+1-Po],所以S2[0,len-1]=S2[k+1-Po,k+len+Po]

    所以S1[k+1,p]=S2[0,P-k-1]

    由于大于P的位置我们还未进行匹配,所以从原串S1的P+1位置开始和模式串的P-k位置开始进行逐一匹配,直到匹配失败,并更新相应的Po位置和最远匹配位置P,此时extend[k+1]=P-k+后来逐一匹配的匹配长度。

    其实,next[]数组的计算过程与extend[]的计算过程基本一致,可以看成是原串S2和模式串S2的扩展KMP进行计算,每次计算extend[k+1]时,next[i](0<=i<=k)已经算出来了,算出extend[k+1]的时候,意味着next[k+1]=extend[k+1]也计算出来了。

    时间复杂度分析

    通过上面的算法可知,我们原串S1的每一个字符串只会进行一次匹配,extend[k+1]的计算可以通过之前extend[i](0<=i<=k)的值得出,由于需要用相同的方法对模式串S2进行一次预处理,所以扩展KMP的时间复杂度为O(l1+l2),其中,l1为原串S1的长度,l2为模式串S2的长度。

    HDU - 2328 

    Corporate Identity

    题意:给你n个字符串,求这n个字符串的最长公共子串
    思路:有多种方面可以做出这道题,我们这里先找出最短的一个母串,然后枚举它的每一个子串,对于每一个子串和原来的母串进行扩展KMP匹配,然后记录匹配的最大值和对应的位置即可,需要注意的时,多个答案时,输出字典序最小的子串。
    //#include<bits/stdc++.h>
    /*
    next[0]=l2; 
    next[i]=max{ k|i<=i+k-1<l2 &&str.substring(i,i+k-1) == str.substring(0,k-1) } 其中str.substring(i, j)表示str从位置i到位置j的子串,如果i>j则,substring为空。
    next[i]表示为以模式串s2中以i为起点的后缀字符串和模式串s2的最长公共前缀长度.
    extend[i]表示为以字串s1中以i为起点的后缀字符串和模式串s2的最长公共前缀长度.
    */
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<map>
    using namespace std;
    const int maxn=100010;   //字符串长度最大值
    const int INF=int(1e9);
    int nxt[maxn],ex[maxn]; //ex数组即为extend数组
    char s1[maxn],s2[maxn];
    char s[5010][210];
    //预处理计算next数组
    void get_next(char *str) {
    	int i=0,j,po,len=strlen(str);
    	nxt[0]=len;//初始化next[0]
    	while(str[i]==str[i+1]&&i+1<len)//计算next[1]
    		i++;
    	nxt[1]=i;
    	po=1;//初始化po的位置
    	for(i=2; i<len; i++) {
    		if(nxt[i-po]+i<nxt[po]+po)//第一种情况,可以直接得到next[i]的值
    			nxt[i]=nxt[i-po];
    		else { //第二种情况,要继续匹配才能得到next[i]的值
    			j=nxt[po]+po-i;
    			if(j<0)j=0;//如果i>po+next[po],则要从头开始匹配
    			while(i+j<len&&str[j]==str[j+i])//计算next[i]
    				j++;
    			nxt[i]=j;
    			po=i;//更新po的位置
    		}
    	}
    }
    //计算extend数组
    bool exkmp(char *s1,char *s2) {
    	int i=0,j,po,len=strlen(s1),l2=strlen(s2);
    	get_next(s2);//计算子串的next数组
    	while(s1[i]==s2[i]&&i<l2&&i<len)//计算ex[0]
    		i++;
    	ex[0]=i;
    	po=0;//初始化po的位置
    	if(ex[0]==l2)
    		return true;
    	for(i=1; i<len; i++) {
    		if(nxt[i-po]+i<ex[po]+po)//第一种情况,直接可以得到ex[i]的值
    			ex[i]=nxt[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的位置
    		}
    		if(ex[i]==l2)
    			return true;
    	}
    	return false;
    }
    void char_(char *str1,char *str,int l,int r) {    //将str字符串的(l,r)赋值给str1 
    	for(int i=l; i<=r; i++) {
    		str1[i-l]=str[i];
    	}
    	str1[r-l+1]='\0';
    	return ;
    }
    int main() {
    	int n;
    	while(~scanf("%d",&n)&&n) {
    		scanf("%d",&n);
    		int Min=INF,pos;
    		for(int i=1; i<=n; i++) {
    			scanf("%s",s[i]);
    			if(strlen(s[i])<Min) {    //找出最短母串 
    				Min=strlen(s[i]);
    				pos=i;
    			}
    		}
    		int Max=0;
    		int l=strlen(s[pos]);
    		int left,right;
    		for(int i=0; i<l; i++) {   //枚举母串的每一个子串 
    			for(int j=i; j<l; j++) {
    				if((j-i+1)<Max) continue;   //剪枝 
    				char_(s1,s[pos],i,j);
    				int flag=true;
    				for(int z=1; z<=n; z++) {  //每一个子串和原来的母串进行匹配 
    					if(z==pos) continue;
    					if(exkmp(s[z],s1))
    						continue;
    					flag=false;
    					break;
    				}
    				if(flag) {
    					if(j-i+1==Max){      //记录所有母串的最长公共子串,长度相同的情况下记录字典序最小的子串 
    						for(int z=0;z+left<=right;z++){
    							if(s[pos][z+left]<s[pos][z+i])
    							break;
    							else{
    								if(s[pos][z+left]>s[pos][z+i]){
    									left=i;
    									right=j;
    									break;
    								}
    							}
    						}
    					}
    					if(j-i+1>Max) {
    						left=i;
    						right=j;
    						Max=max(Max,j-i+1);
    					}
    				}
    			}
    		}
    		if(Max==0)
    			printf("IDENTITY LOST\n");
    		else {
    			for(int i=left; i<=right; i++) {
    				printf("%c",s[pos][i]);
    			}
    			printf("\n");
    		}
    	}
    	return 0;
    }

     

    展开全文
  • 首先看了几篇博客,发现还得耐下心来理解,动手画图 ,才能理解俩.../*扩展kmp */ /*一开始假设求出了 next数组,然后去求extend数组,然后方法一样 next数组可以自己求自己*/ #include<stdio.h> #include&l...

    首先看了几篇博客,发现还得耐下心来理解,动手画图 ,才能理解俩字符串还有数组之间神奇的关系

    这篇博客图不错:https://segmentfault.com/a/1190000008663857

    /*扩展kmp */
    /*一开始假设求出了 next数组,然后去求extend数组,然后方法一样
    next数组可以自己求自己*/
    #include<stdio.h>
    #include<string.h>
    #define S 1000
    #define T 1000
    char s[S],t[T];
    /* 母串  子串*/
    int extend[S],nex[T],p,a;/*extend[a]=p  p最大值 */
    /* extend[i]数组 :s母串的 i开头后缀串 与 t子串的最长公共前缀
       nex[i] 数组:t子串以 i开头后缀串 与 t子串的最长公共前缀
    */
    void getnext()
    {
        a=0,p=0;
        int m=strlen(t);
        memset(nex,0,sizeof(nex));
        nex[0]=m;/*自己本身作为前后缀*/
        for(int i=1;i<m;i++)
        {
            if(i>=p||i+nex[i-a]>=p)
            {
                if(i>=p)
                    p=i;
                while(p<m&&t[p]==t[p-i])
                    p++;
                nex[i]=p-i;
                a=i;
            }
            else
                nex[i]=nex[i-a];
        }
    }
    void getextend()
    {
        getnext();
        a=0,p=0;
        int n=strlen(s),m=strlen(t);
        for(int i=0;i<n;i++)
        {
            if(i>=p||i+nex[i-a]>=p)/*i-a的含义,多看图*/
            {
                if(i>=p)
                    p=i;
                while(p<n&&p-i<m&&s[p]==t[p-i])/*可以继续往后匹配*/
                    p++;
                extend[i]=p-i;
                a=i;/*记录下标*/
            }
            else
                extend[i]=p-i;
        }
    //    for(int i=0;i<n;i++)
    //        printf("%d ",extend[i]);
    //    printf("\n");
    //    for(int i=0;i<m;i++)
    //        printf("%d ",nex[i]);
    //    printf("\n");
        return ;
    }
    int main()
    {
        while(~scanf("%s%s",s,t))
        {
            getextend();
        }
        return 0;
    }
    

     

    展开全文
  • 几篇关于拓展KMP的论文,字符串题目的必备工具
  • 拓展KMP算法详解

    千次阅读 2017-08-22 10:37:08
    算法描述:设字符串T,长度为n,字符串S,长度为m。在线性时间内求出T的每一个后缀所对应S的最长前缀。 假设T=“AAAAB”,S="AAAA"。 我们从第一位开始匹配,匹配结果存放到ext数组中。显然ext【0】=4,然后我们就去...
  • 扩展KMP

    2018-10-08 08:42:51
    关于扩展KMP算法写的比较好的文章:   https://segmentfault.com/a/1190000008663857 例题: HDU 6153 题意: 每组给你两个字符串s1和s2,求s2的所有后缀在s1中出现的频率,频率再乘以对应的后缀的长度,累加...
  • KMP与扩展KMP算法

    2019-09-09 22:33:55
    注意这里是数目,与KMPNext是下标不同。 注意是子串匹配 例如:字符串abcdaabcab的特征向量是(0,0,0,0,1,1,2,3,1,2) 对于每个字符,暴力比较耗时。可看出每个字符的特征值可以由它之前的字符推出:用next[i]...
  • 扩展KMP】【模板】讲解

    千次阅读 2019-01-24 21:18:42
    扩展KMP】【模板】讲解 摘自 拓展kmp算法总结 1、扩展KMP是什么?解决何种问题?与KMP算法的异同? 拓展kmp是对KMP算法的扩展,它解决如下问题: 定义母串S,和字串T,设S的长度为n,T的...
  • 扩展kmp详解

    千次阅读 2016-10-22 10:08:14
    算法总结第二弹,上次总结了下kmp,...拓展kmp是对KMP算法的扩展,它解决如下问题: 定义母串S,和字串T,设S的长度为n,T的长度为m,求T与S的每一个后缀的最长公共前缀,也就是说,设extend数组,extend[i]表示T与
  • KMP+扩展KMP

    2019-04-30 18:37:22
    KMP KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题(或者是出现次数等的问题)。说简单点就是我们平时常说的关键字搜索。 首先,对于这个问题有一个很单纯的想法:从左到右一个个匹配,...
  • poj3461 (KMP&&扩展KMP

    万次阅读 2017-05-21 12:50:51
    题目大意是求串w在串t中出现的次数,例如aa在aaa中出现了两次. Sample Input 3 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN ...//kmp算法 #include #include #include using namespace std; const
  • 扩展KMP复习小记

    千次阅读 2016-12-04 10:35:10
    简介KMP大家都耳熟能详,扩展KMP只是一个扩展版而已,字面意思啦! 我记得以前打过这个复习小记的,但是不知为何失踪了。KMP与扩展KMP的对比KMP的next[i]表示从1到i的字符串s,前缀和后缀的最长重叠长度。 EXKMP的...
  • 扩展KMP的讲解与应用

    千次阅读 2013-11-11 12:29:29
    http://www.isnowfy.com/kmp-and-extend-kmp/ ------简单比较下KMP,扩展KMP和最小表示法 http://3214668848.blog.163.com/blog/static/48764919200910152452182/ -----扩展KMP算法(Extend KMP)  ...
  • hdu3613之扩展KMP

    千次阅读 2013-07-19 22:08:45
    Best Reward Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 364 Accepted Submission(s): 144 扩展KMP Problem Description After an uphill
  • kuangbin专题

    千次阅读 2019-04-03 18:41:54
    https://vjudge.net/article/371 专题一简单搜索 专题四 最短路练习 专题五 并查集 专题六 最小生成树 专题十六 KMP & 扩展KMP & Manacher 专题十七 AC自动机 ...
  • 扩展kmp 模板

    千次阅读 2013-05-24 23:44:31
    对于扩展kmp,现在还没有进行实用,所以先将模板打好基础,理解清楚每一步,这样日后应用就轻松点了。 对于这个模板,我觉得主要以理解扩展kmp为主,赛场实战的时候可以适当简化,这个模板对着 刘琼雅的 那个...
  • 扩展KMP算法

    千次阅读 2013-09-10 16:50:07
    扩展KMP:给出模板串S和子串T,长度分别为Slen和Tlen,要求在线性时间内,对于每个S[i](0度,记为extend[i](或者说,extend[i]为满足S[i..i+z-1]==T[0..z-1]的最大的z值)。扩展KMP可以用来解决很多字符串问题,如...
  • #include char s1[1000],s2[1000]; int next[1000],ex[1000]; void exkmp(char s1[],char s2[],int ex[],int next[]) { int i,j,p; i = j = 0; p = -1; while(s1[i]!='\0') { if( p == -1) ...
  • KMP/KMP扩展】目录

    2017-03-29 13:23:39
    KMP: hdu 1686 :简单题 hdu 2087 :简单题 hdu 3746 :需透彻理解next数组的含义 hdu 1358 :还是需要透彻理解next数组的含义 hdu 3336 :有点难度,KMP+DP
1 2 3 4 5 ... 20
收藏数 9,234
精华内容 3,693
热门标签
关键字:

扩展kmp