Php文档 Php问答行业资讯 Php论坛 Php手册 Php博客

游戏榜单

软件榜单

关闭导航

热搜榜

热门下载

热门标签

关闭搜索

php爱好者> php文档>KMP，Extended KMP

KMP，Extended KMP

时间：2010-11-12 来源：LitIce

字串a0,a1,a2,a3,a4...an

------------------------------------------------------------------------------

KMP:

记录fail[i]记录假如i+1匹配失败应该退回到哪里。。。

同时也表示了a(i-fail[i]+1)..ai与a0,a1...a(fail[i])匹配。即字串后缀与前缀的匹配。

假如fail[10]=5

a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10

a5 a6 a7 a8 a9 a10

那么当我们匹配 ci!=a11时我们就没有必要重新开始只需从a5开始因为

a5 a6 a7 a8 a9 a10与a1 a2 a3 a4 a5已经匹配

-------------------------------------------------------------------------------

Extended KMP:

记录一个la[i]长度数组。表示从i开始字串的前缀和字串前缀能够匹配的最大长度。

a0...a(la[i]-1) 与 ai...a(la[i]+i-1) 匹配

做法：

先预处理出la[0]和la[1]; 令 k=1

a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10

ck ck+1 ck+2 ck+3 ck+4 ck+5 ck+6ck+7 ck+8 ck+9 ck+10

当前做i时，前i-1的la值都是求好的

假设i=ck+t

那么la[i]的计算就可以用上la[i-k]即la[t]的值!!

（显然ck+t..c(xx) 已经和 a(t)..a(xx)匹配了！！！所以la[t]的值就可以用在la[k+t]上！）

假如k的匹配长度为len,而i+la[t]-1仍旧小于len ,那么la[i]就就只能等于la[t];

如果 i+la[t]-1 大于len ，那么就需要继续向下匹配到不能够匹配，

更新k值

----------------------------------------------------------------------------------

两个算法的优化之处都是把之前计算过的有用值记录下来。从而避免重复计算提高效率

-----------------------------------------------------------------------------------

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3673

题目给出模式串A，匹配串B，求A在B中的匹配长度。注意这里的A可以旋转。

1 3 2

2 3 2 1 3 2 1 5

在这里 3 2 1 3 2 1 可以被 1 3 2 匹配。

我们发现到这样一个串一定可以被分成三个部分

3 2 1 3 2 1 5

第一部分是A串的后缀。第二部分是若干个A串。第三部分是A的前缀。

注意到第一部分同时是自己这个串的后缀。第三部分同时自己这个串的前缀。

注意到上面红字部分。这是我们显然要选择Extended KMP

我们只要对AB做一次Extended KMP。就可以完成第三部分。

将AB串倒过来再做一次Extended KMP。可以完成第一部分。

剩余的就是一遍扫描就可以了。

代码

#include<iostream>
#include<cstdio>
using namespace std;

int a[1001],b[1000001];
int la[1000001],pl[1000001],pr[1000001];
int n,m,tot,ans,len,l,k,j,t,now;
void swap(int &a,int &b)
{
     t=a;a=b;b=t;
}
int solve()
{
    
    la[0]=n;
    j=0;
    while (j<n-1 && a[j+1]==a[j]) ++j;
    la[1]=j;k=1;
    for (int i=2;i<n;++i)
    {
        len=k+la[k]-1;l=la[i-k];
        if (i+l-1<len) la[i]=l;
        else
        {
            j=0;
            if (len-i+1>j) j=len-i+1;
            while (i+j<n && a[i+j]==a[j]) ++j;
            la[i]=j;k=i;
        }
    }
    
    
    j=0;
    while (j<n && j<m && a[j]==b[j]) ++j;
    pl[0]=j;k=0;
    for (int i=1;i<m;++i)
    {
        len=k+pl[k]-1;l=la[i-k];
        if (i+l-1<len) pl[i]=l;
        else
        {
            j=0;
            if (len-i+1>j) j=len-i+1;
            while (i+j<m && j<n && b[i+j]==a[j]) ++j;
            pl[i]=j;k=i;
        }
    }
}
int main()
{
    freopen("3298.in","r",stdin);
    freopen("3298.out","w",stdout);
    while (cin>>n>>m)
    {
          ans=0;
          for (int i=0;i<n;++i) scanf("%d",&a[i]);
          for (int i=0;i<m;++i) scanf("%d",&b[i]);
          solve();
          for (int i=0;i<m;++i) pr[i]=pl[i];
          for (int i=0;i<n/2;++i) swap(a[i],a[n-i-1]);
          for (int i=0;i<m/2;++i) swap(b[i],b[m-i-1]);
          solve();
    
          for (int i=0;i<m/2;++i) swap(pl[i],pl[m-1-i]);
         
          for (int i=0;i<m;++i)
          {
              if ( (i-n<0 ||  pr[i-n]!=n ) && pr[i]==n)
              {
                        now=i;
                        while (now<m && pr[now]==n) now+=n;
                        tot=now-i;
                        if (now<m) tot+=pr[now];
                        if (i>=1) tot+=pl[i-1];
                        if (tot>ans) ans=tot;
              } 
          }
              if (ans==0) cout<<"bad"<<endl;else 

                    cout<<ans<<endl;
    }
    return 0;
}