POJ3167 Cow Patterns [KMP]

　　感觉是不太好想的一道题，看完之后能想到是KMP，按照自己的想法敲了出来，但一直过不了。后来在网上搜题解搜到了一篇国家集训队的论文《由图论问题浅析算法优化》，论文中提到了这道题，想法很巧妙，类似于枚举，再加上KMP的优化。因为S较小(1~25)，只要枚举模式串中的数字和匹配串中的数字的对应关系并且满足大小顺序关系就可以确定下来这个子串是否符合要求，具体的过程可以去看一下论文，这个算法的本质还是枚举，只是在枚举中进行了优化，并且使用KMP优化来快速找到符合对应关系的子串的位置，我的程序在POJ上跑了一秒多点，应该可以再优化。

　　但是上面的算法还是有缺点的，其复杂度是O(S*S*(N+M))，当S比较小时可以使用，一旦S比较大，这个算法是很容易被卡掉的。看到网上有代码是和自己一样的思路是用KMP过的，于是又拿出了自己的代码调了大半天，终于是过了，复杂度是O((N+M)*Log(S))，在POJ上跑了200多ms，效率还算比较好的，算法也是是基于KMP的。

　　有一个很显然的结论，只要这两个串中对应位置的数字前面比它小以及和它相等的数字数都相等，这两个串就可以认为是相等的，比如对于12232和23353或者37787等等都可以看作相等的串，三个串每个数字前面比它小的数字数构成的串都是01131，前面和它相等的数字数构成的串都是00102，所以只要将KMP的判断相等的条件改为这两个串对应相等就可以了。需要注意的是在串的匹配过程中需要动态的删除和添加，保证当前保存的信息是正在进行匹配的子串信息，一开始就是因为这个地方没有处理好调试了很久。因为要频繁的求串前面比它小的数字的个数，而且是动态的，所以要用树状数组或者线段树来维护，将复杂度从S降低到Log(S)。

　　两段代码都发上来吧，如果觉得我上面说的不清楚看下代码应该就明白了。

枚举+KMP优化(1110ms)：

#include <string.h>
#include <stdio.h>
#define MAXN 100005
#define MAXM 25005
#define INF 0x3fffffff

int n,m,s;
int cow[MAXN],pot[MAXM];
int flg[30],maxx[MAXN],maxy[MAXN];
int st[MAXN],rt[MAXM],next[MAXM];
void KMP(int step,int x){
    for(int i=1;i<=m;i++)rt[i]=(pot[i]==step)?x:0;
    for(int i=1;i<=n;i++)st[i]=(cow[i]==x)?x:0;
    next[1]=0;
    for(int i=2,j=0;i<=m;i++){
        while(j>0&&rt[i]!=rt[j+1])j=next[j];
        if(rt[i]==rt[j+1])j++;
        next[i]=j;
    }
    for(int i=1,j=0;i<=n;i++){
        while(j>0&&st[i]!=rt[j+1])j=next[j];
        if(st[i]==rt[j+1])j++;
        if(j==m){
            maxy[i-m+1]=x;
            j=next[j];
        }
    }
}
int main(){
//freopen("test.in","r",stdin);
    while(scanf("%d%d%d",&n,&m,&s)!=EOF){
        memset(flg,0,sizeof flg);
        for(int i=1;i<=n;i++){
            scanf("%d",&cow[i]);
        }
        for(int i=1;i<=n;i++){
            maxx[i]=0;
        }
        for(int i=1;i<=m;i++){
            scanf("%d",&pot[i]);
            flg[pot[i]]=1;
        }
        for(int i=1;i<=s;i++){
            if(!flg[i])continue;
            //枚举第i大的数是j
            for(int j=1;j<=n;j++)maxy[j]=INF;
            for(int j=1;j<=s;j++)KMP(i,j);
            for(int j=1;j<=n;j++){
                //maxy必须比maxx大,否则表示第i大的数比第i-1大的数小,置为无穷大
                if(maxy[j]<=maxx[j])maxx[j]=INF;
                else maxx[j]=maxy[j];
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
            if(maxx[i]!=INF)ans++;
        printf("%d\n",ans);
        for(int i=1;i<=n;i++){
            if(maxx[i]!=INF)printf("%d\n",i);
        }
    }
    return 0;
}

KMP+树状数组优化(282ms)：

#include <string.h>
#include <stdio.h>
#include <algorithm>
#define MAXN 100005
#define MAXM 25005
#define INF 0x3fffffff

int n,m,s,ans[MAXN],anss;
int cow[MAXN],pot[MAXM];

int tot[30];
int lowbit(int x){
    return x&-x;
}
void upd(int x,int a){
    if(x==0)return;
    while(x<s+1)tot[x]+=a,x+=lowbit(x);
}
int sum(int x){
    int ans=0;
    while(x>0)ans+=tot[x],x-=lowbit(x);
    return ans;
}

int next[MAXM],p1[MAXM],p2[MAXM];
void KMP(){
    memset(tot,0,sizeof tot);
    for(int i=1;i<=m;i++){
        p1[i]=sum(pot[i]-1);
        p2[i]=sum(pot[i]);
        upd(pot[i],1);
    }
    memset(tot,0,sizeof tot);
    next[1]=0;
    for(int i=2,j=0;i<=m;i++){
        while(j>1&&(sum(pot[i])!=p2[j+1]||sum(pot[i]-1)!=p1[j+1])){
            for(int k=i-j;k<i-next[j];k++)upd(pot[k],-1);
            j=next[j];
        }
        if(sum(pot[i])==p2[j+1]&&sum(pot[i]-1)==p1[j+1])j++;
        next[i]=j;
        upd(pot[i],1);
    }

    memset(tot,0,sizeof tot);
    anss=0;
    for(int i=1,j=0;i<=n;i++){
        while(j>0&&(sum(cow[i])!=p2[j+1]||sum(cow[i]-1)!=p1[j+1])){
            for(int k=i-j;k<i-next[j];k++)upd(cow[k],-1);
            j=next[j];
        }
        if(sum(cow[i])==p2[j+1]&&sum(cow[i]-1)==p1[j+1])j++;
        if(j==m){
            //这个地方没写对调了好久
            for(int k=i-j+1;k<=i-next[j];k++)upd(cow[k],-1);
            ans[anss++]=i-m+1;
            j=next[j];
        }
        upd(cow[i],1);
    }
}
int main(){
//freopen("test.in","r",stdin);
    while(scanf("%d%d%d",&n,&m,&s)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%d",&cow[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%d",&pot[i]);
        }
        KMP();
        printf("%d\n",anss);
        for(int i=0;i<anss;i++){
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}