精华内容
下载资源
问答
  • 扩展kmp

    2020-06-19 15:35:17
    网上有详细讲解,我个人觉得kmp比扩展kmp要难看的,扩展kmp主要用来解决主串的所有后缀与子串t最长的公共前缀问题,扩展kmp也能找到子串在主串中是否出现,因为如果长度为子串t的长度,那么肯定就能说明子串t在主串...

    网上有详细讲解,我个人觉得kmp比扩展kmp要难看的,扩展kmp主要用来解决主串的所有后缀与子串t最长的公共前缀问题,扩展kmp也能找到子串在主串中是否出现,因为如果长度为子串t的长度,那么肯定就能说明子串t在主串中出现过。
    借鉴了博客
    Corporate Identity这道题的做法,顺便学习了一下扩展kmp,其实这道题暴力也能过的,只不过好麻烦,字符串题码力就是大。

    #include<iostream>
    #include<string.h>
    using namespace std ;
    const int maxn = 1e6+10;
    int nt[maxn],ex[maxn];
    char s[5000][300];
    char ss[maxn];
    void getnext(char * s)
    {
        int i=0,n;
        n = strlen(s);
        nt[0] = n;
        while(i+1<n&&s[i]==s[i+1]) i++;
        nt[1] = i;
        int po = 1;
        for(int i=2;i<n;i++)
        {
            if(i+nt[i-po]<nt[po]+po)
                nt[i] = nt[i-po];
            else
            {
                int j = nt[po] + po - i;
                if(j<0) j = 0;
                while(i+j<n&&s[j]==s[i+j]) j++;
                nt[i] = j;
                po = i;
            }
        }
    }
    int exkmp(char *s,char *t)
    {
         int i = 0 , n1 = strlen(s) , n2 = strlen(t);
         getnext(t);
         while(i<n1&&i<n2&&s[i]==t[i]) i++;
         ex[0] = i;
         int po = 0;
         if(ex[0]==n2) return 1;
         for(int i=1;i<n1;i++)
         {
             if(nt[i-po]+i<ex[po]+po)
                ex[i] = nt[i-po];
             else
             {
                 int j = ex[po] + po - i;
                 if(j<0) j = 0;
                 while(i+j<n1&&s[i+j]==t[j]) j++;
                 ex[i] = j;
                 po = i;
             }
             if(ex[i]==n2) return 1;
         }
         return 0;
    }
    void quchar(char *s,char *ss,int l,int r)
    {
        for(int i=l;i<=r;i++) s[i-l] =  ss[i];
        s[r-l+1] ='\0';
        return ;
    }
    int main()
    {
         int n ;
         while(~scanf("%d",&n)&&n)
         {
             int mn = 1e9,pos;
             for(int i=1;i<=n;i++)
             {
                 scanf("%s",s[i]);
                 if(strlen(s[i])<mn)
                 {
                     mn = strlen(s[i]);
                     pos = i;
                 }
             }
             int mx =  0,l,r;
             int len = strlen(s[pos]);
             for(int i=0;i<len;i++)
             {
                 for(int j=0;j<len;j++)
                 {
                     if(j-i+1<mx) continue;
                      int f = 0;
                      quchar(ss,s[pos],i,j);
                      for(int k=1;k<=n;k++)
                      {
                          if(k==pos) continue;
                          if(!exkmp(s[k],ss))
                          {
                              f= 1; break;
                          }
                      }
                      if(!f)
                      {
                          if(j-i+1>mx)
                          {
                              mx = j-i+1;
                              l = i;
                              r = j;
                          }
                          else if(j-i+1==mx)
                          {
                              for(int k=0;k+l<=r;k++)
                              {
                                  if(s[pos][k+l]<s[pos][k+i])
                                   break;
                                   else
                                   {
                                       if(s[pos][k+l]>s[pos][k+i])
                                       {
                                           l = i;
                                           r = j;
                                           break;
                                       }
                                   }
                              }
                          }
                      }
                 }
             }
             if(mx==0) printf("IDENTITY LOST\n");
             else
             {
                 for(int i=l;i<=r;i++) printf("%c",s[pos][i]);
                 printf("\n");
             }
         }
    }
    
    
    展开全文
  • 扩展KMP

    2019-08-06 23:29:19
    之前写过扩展kmp的题,但记忆不太深刻又忘记了,自己的模板上也没解释,那么这里就写一下吧,弥补之前的懒惰。 初学者不建议看。 自我对扩展KMP的理解: 自我觉得扩展KMP与mannacher算法都差不多,都是利用...

    前述:

    之前写过扩展kmp的题,但记忆不太深刻又忘记了,自己的模板上也没解释,那么这里就写一下吧,弥补之前的懒惰。

    初学者不建议看。

    自我对扩展KMP的理解:     

            自我觉得扩展KMP与mannacher算法都差不多,都是利用之前已经计算过的地方,去获取一个已经计算过的长度,然后再暴力计算未计算的长度。而kmp与扩展kmp有很大的不同

    EXkmp:s[i...k+i-1]与s[0...k-1]相等的最大的k  (普通kmp是以i为后缀的相同的最长前缀,而扩展kmp是i为前缀的最长前缀)


    例题

    洛谷例题:P5410 【模板】扩展 KMP

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+10;
    char a[maxn],b[maxn];
    int exb[maxn],exkmp[maxn];
    /*
    EXkmp:s[i...k+i-1]与s[0...k-1]相等的最大的k  (普通kmp是以i为后缀的相同的最长前缀,而扩展kmp是i为前缀的最长前缀)
    exb[i]:b[i...k+i-1]与b[0...k-1]相等的最大的k
    exkmp[i]:a[i..k+i-1]与b[0..k-1]相同的最大的k
    */
    void pre_kmp(char s[],int ls,int next[])//预处理字符串b的kmp
    {
        int id,maxr;//最长扩展的i和延申的位置maxr
        next[0]=ls;
        id=-1,maxr=-1;
        for(int i=1;i<ls;++i)
        {
            int qs;//next[i]的值
            if(maxr-i+1<=0)//不在可以扩展的范围,那就自己先为0
                qs=0;
            else
                qs=min(maxr-i+1,next[i-id]);//可扩展,取min以防出边界
            while(i+qs<ls&&s[i+qs]==s[qs]) ++qs;//暴力扩展未知的
            next[i]=qs;
            if(qs+i-1>maxr){
                maxr=qs+i-1;
                id=i;
            }
        }
    }
    void EXkmp(char a[],int la,char b[],int lb,int next[],int exkmp[])
    {
        pre_kmp(b,lb,next);
        int id=-1,maxr=-1;
        for(int i=0;i<la;++i){
            int qs;
            if(maxr-i+1<=0) qs=0;
            else qs=min(maxr-i+1,next[i-id]);
            while(i+qs<la && qs<lb && a[i+qs]==b[qs]) ++qs;
            exkmp[i]=qs;
            if(qs+i-1>maxr){
                maxr=qs+i-1;
                id=i;
            }
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);cin.tie(0);
        cin>>a>>b;
        int lb=strlen(b);
        int la=strlen(a);
        EXkmp(a,la,b,lb,exb,exkmp);
    //    pre_kmp(b,lb,exb);
        for(int i=0;i<lb;++i)
            cout<<exb[i]<<" ";
        cout<<endl;
        for(int i=0;i<la;++i)
            cout<<exkmp[i]<<" ";
        cout<<endl;
        return 0;
    }

    hdu 6629:string matching

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+10;
    typedef long long ll;
    char s[maxn];
    ll exs[maxn];
    void pre_kmp(char s[],ll ls,ll next[])//预处理字符串b的kmp
    {
        ll id,maxr;//最长扩展的i和延申的位置maxr
        next[0]=ls;
        id=-1,maxr=-1;
        for(ll i=1; i<ls; ++i)
        {
            ll qs;//next[i]的值
            if(maxr-i+1<=0)//不在可以重用数据的范围
                qs=0;
            else
                qs=min(maxr-i+1,next[i-id]);//可扩展,取min以防出边界
            while(i+qs<ls&&s[i+qs]==s[qs]) ++qs;
            next[i]=qs;
            if(qs+i-1>maxr)
            {
                maxr=qs+i-1;
                id=i;
            }
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin>>t;
        while(t--)
        {
            cin>>s;
            ll ans=0;
            ll ls=strlen(s);
            pre_kmp(s,ls,exs);
            for(ll i=1; i<ls; ++i)
            {
                if(i+exs[i]==ls)
                    ans+=exs[i];
                else
                    ans+=exs[i]+1;
            }
            cout<<ans<<endl;
        }
    
        return 0;
    }
    

     

    展开全文
  • 扩展 KMP

    2019-10-02 21:20:31
    扩展 KMP 一:算法流程 二:代码 扩展 KMP 来源 问题定义:给定两个字符串 S 和 T(长度分别为 n 和 m),下标从 0 开始,定义 extend[i] 等于 S[i]... S[n-1] 与 T 的最长相同前缀的长度,求出所有的 ext...

    扩展 KMP

    来源
    问题定义:给定两个字符串 S 和 T(长度分别为 n 和 m),下标从 0 开始,定义 extend[i] 等于 S[i]... S[n-1] 与 T 的最长相同前缀的长度,求出所有的 extend[i]。举个例子,看下表:

    i 0 1 2 3 4 5 6 7
    S a a a a a b b b
    T a a a a a c
    extend[i] 5 4 3 2 1 0 0 0

    为什么说这是 KMP 算法的扩展呢?显然,如果在 S 的某个位置 i 有 extend[i] 等于 m,则可知在 S 中找到了匹配串 T,并且匹配的首位置是 i。而且,扩展 KMP 算法可以找到 S 中所有 T 的匹配。接下来具体介绍下这个算法。

    一:算法流程

    20180412_01.png
    如上图,假设当前遍历到 S 串位置 i,即 extend[0]...extend[i - 1] 这 i 个位置的值已经计算得到。设置两个变量,a 和 p。p 代表以 a 为起始位置的字符匹配成功的最右边界,也就是 "p = 最后一个匹配成功位置 + 1"。相较于字符串 T 得出,S[a...p) 等于 T[0...p-a)

    再定义一个辅助数组 int next[],其中 next[i] 含义为:T[i]... T[m - 1] 与 T 的最长相同前缀长度,m 为串 T 的长度。举个例子:

    i 0 1 2 3 4 5
    T a a a a a c
    next[i] 6 4 3 2 1 0

    20180412_02.png
    S[i]对应 T[i - a],如果 i + next[i - a] < p,如上图,三个椭圆长度相同,根据 next 数组的定义,此时extend[i] = next[i - a]。

    (3)
    20180412_03.png
    如果 i + next[i - a] == p 呢?如上图,三个椭圆都是完全相同的,S[p] != T[p - a]且T[p - i] != T[p - a],但S[p]有可能等于 T[p - i],所以我们可以直接从 S[p]T[p - i] 开始往后匹配,加快了速度。

    (4)

    20180412_04.png
    如果 i + next[i - a] > p 呢?那说明 S[i...p)与T[i-a...p-a) 相同,注意到 S[p] != T[p - a]且T[p - i] == T[p - a] ,也就是说 S[p] != T[p - i],所以就没有继续往下判断的必要了,我们可以直接将 extend[i] 赋值为 p - i

    (5)最后,就是求解 next 数组。我们再来看下next[i]与extend[i]的定义:

    • ext[i]T[i]...T[m - 1] 与 T 的最长相同前缀长度;
    • extend[i]S[i]...S[n - 1] 与 T 的最长相同前缀长度。
      恍然大悟,求解next[i]的过程不就是 T 自己和自己的一个匹配过程嘛,下面直接看代码。

    二:代码

    #include <iostream>
    #include <string>
    
    using namespace std;
    
    /* 求解 T 中 next[],注释参考 GetExtend() */
    void GetNext(string & T, int & m, int next[])
    {
        int a = 0, p = 0;
        next[0] = m;
    
        for (int i = 1; i < m; i++)
        {
            if (i >= p || i + next[i - a] >= p)
            {
                if (i >= p)
                    p = i;
    
                while (p < m && T[p] == T[p - i])
                    p++;
    
                next[i] = p - i;
                a = i;
            }
            else
                next[i] = next[i - a];
        }
    }
    
    /* 求解 extend[] */
    void GetExtend(string & S, int & n, string & T, int & m, int extend[], int next[])
    {
        int a = 0, p = 0;
        GetNext(T, m, next);
    
        for (int i = 0; i < n; i++)
        {
            if (i >= p || i + next[i - a] >= p) // i >= p 的作用:举个典型例子,S 和 T 无一字符相同
            {
                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]** = next[i - a];
        }
    }
    
    int main()
    {
        int next[100];
        int extend[100];
        string S, T;
        int n, m;
        
        while (cin >> S >> T)
        {
            n = S.size();
            m = T.size();
            GetExtend(S, n, T, m, extend, next);
    
            // 打印 next
            cout << "next:   ";
            for (int i = 0; i < m; i++)
                cout << next[i] << " ";
     
            // 打印 extend
            cout << "\nextend: ";
            for (int i = 0; i < n; i++)
                cout <<  **extend[i]** << " ";
    
            cout << endl << endl;
        }
        return 0;
    }

    数据测试如下:

    aaaaabbb
    aaaaac
    next:   6 4 3 2 1 0
    extend: 5 4 3 2 1 0 0 0
    
    abc
    def
    next:   3 0 0
    extend: 0 0 0

    转载于:https://www.cnblogs.com/tttfu/p/11309577.html

    展开全文

空空如也

空空如也

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

扩展kmp