KMP--君住长江头，我住长江尾，日日思君不见君，共饮长江水

POJ 3461: Oulipo

题意：

求出第一个串在第二个串中的出现次数...

分析：

KMP板子题...

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
//眉眼如初，岁月如故

const int maxn=1000000+5;

int cas,lens,lenp,nxt[maxn];

char s[maxn],p[maxn];

inline void getnxt(void){
    nxt[0]=nxt[1]=0;int k;
    for(int i=1;i<lenp;i++){
        k=nxt[i];
        while(k&&p[k+1]!=p[i+1])
            k=nxt[k];
        if(p[k+1]==p[i+1])
            nxt[i+1]=k+1;
        else
            nxt[i+1]=0;
    }
}

inline void kmp(void){
    int ans=0,posp=1,poss=1;
    while(poss<=lens){
        if(p[posp]==s[poss])
            posp++,poss++;
        else if(posp==1)
            poss++;
        else
            posp=nxt[posp-1]+1;
        if(posp==lenp+1)
            ans++,posp=nxt[posp-1]+1;
    }
    printf("%d
",ans);
}

signed main(void){
    scanf("%d",&cas);
    while(cas--){
        memset(nxt,0,sizeof(nxt));
        scanf("%s%s",p+1,s+1);
        lenp=strlen(p+1);lens=strlen(s+1);
        getnxt();kmp();    
    }
    return 0;
}//Cap ou pas cap. Pas cap.

POJ 2406: Power Strings

题意：

求出每个串的最短循环节出现次数...

分析：

此题两种解法...然而本质上是一样的...

No.1 Hash

对于一个串其前缀A和后缀B相同并且有重叠，并且len%strlen(str-B)==0，那么str-B一定是循环节...所以我们可以用hash水过...

No.2 next数组...

然而更机智的做法是next数组...

代码：

No.1 Hash

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
const int maxn=1000000+5,MOD=100000007;
char str[maxn];
int len,ans;
unsigned int hash[maxn],pow[maxn]; 
signed main(void){
    pow[0]=(long long)1;
    for(int i=1;i<maxn;i++)
        pow[i]=(pow[i-1]*30)%MOD;
    while(scanf("%s",str+1)&&str[1]!='.'){
        len=strlen(str+1),hash[0]=0,ans=1;
        for(int i=1;i<=len;i++)
            hash[i]=(hash[i-1]*30%MOD+str[i]-'a'+1)%MOD;
        for(int i=1;i<len;i++){
            if(len%(len-i)==0){
                if(hash[i]%MOD==(hash[len]-hash[len-i]*pow[i]%MOD+MOD)%MOD){
                    ans=len/(len-i);
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

No.2 next数组

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
//眉眼如初，岁月如故

const int maxn=1000000+5;

int len,nxt[maxn];

char str[maxn];

inline void getnxt(void){
    nxt[0]=nxt[1]=0;int k;
    for(int i=1;i<len;i++){
        k=nxt[i];
        while(k&&str[k+1]!=str[i+1])
            k=nxt[k];
        if(str[k+1]==str[i+1])
            nxt[i+1]=k+1;
        else
            nxt[i+1]=0;
    }
}

signed main(void){
    while(scanf("%s",str+1)&&str[1]!='.'){
        len=strlen(str+1);getnxt();
        if(len%(len-nxt[len])==0)
            printf("%d
",len/(len-nxt[len]));
        else
            puts("1");
    }
    return 0;
}//Cap ou pas cap. Pas cap.

POJ 2752: Seek the Name, Seek the Fame

题意：

输出所有s的合法前缀，合法前缀的定义为前缀等于后缀...

分析：

不断nxt...

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
//眉眼如初，岁月如故 

const int maxn=400000+5;

int len,tail,nxt[maxn],stk[maxn];

char str[maxn];

inline void getnxt(void){
    nxt[0]=nxt[1]=0;int k;
    for(int i=1;i<len;i++){
        k=nxt[i];
        while(k&&str[k+1]!=str[i+1])
            k=nxt[k];
        if(str[k+1]==str[i+1])
            nxt[i+1]=k+1;
        else
            nxt[i+1]=0;
    }
}

signed main(void){
    while(scanf("%s",str+1)!=EOF){
        len=strlen(str+1);getnxt();tail=0;stk[++tail]=len;
        while(nxt[len])
            stk[++tail]=nxt[len],len=nxt[len];
        for(int i=tail;i>=1;i--)
            printf("%d ",stk[i]);
        puts("");
    }
    return 0;
}//Cap ou pas cap. Pas cap.

POJ 3167: Cow Patterns

题意：

给出两个串，如果a和b匹配当且仅当ab中的每个对应位置的数字rank1和rank2相同，rank1代表当前元素前面小于他的元素个数，rank2代表当前元素前面等于他的元素个数，求出匹配串和模式串的匹配位置（开头位置）

 分析：

KMP…裸的KMP…就是计算一下rank就好… 
因为数字不会超过25，所以直接暴力求rank就好…

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
const int maxn=100000+5,maxk=25000+5,maxs=25+5;
int n,k,s,a[2][maxn],nxt[maxk],num[2][maxn][maxs],vis[maxk];
inline int rank1(int len,int en,int id){
    int st=en-len,ans=0;
    for(int i=1;i<a[id][en];i++)
        ans+=num[id][en][i]-num[id][st][i];
    return ans;
}
inline int rank2(int len,int en,int id){
    return num[id][en][a[id][en]]-num[id][en-len][a[id][en]];
}
inline void getnext(void){
    nxt[0]=nxt[1]=0;int p;
    for(int i=1;i<k;i++){
        p=nxt[i];int a=rank1(p+1,p+1,1),b=rank1(p+1,i+1,1),c=rank2(p+1,p+1,1),d=rank2(p+1,i+1,1);
        while(p&&(a!=b||c!=d))
            p=nxt[p],a=rank1(p+1,p+1,1),b=rank1(p+1,i+1,1),c=rank2(p+1,p+1,1),d=rank2(p+1,i+1,1);
        if(rank1(p+1,p+1,1)==rank1(p+1,i+1,1)&&rank2(p+1,p+1,1)==rank2(p+1,i+1,1))
            nxt[i+1]=p+1;
        else
            nxt[i+1]=0;
    }
}
inline void kmp(void){
    int posa=1,posb=1,ans=0,stk[maxn];
    while(posa<=n){
        if(rank1(posb,posa,0)==rank1(posb,posb,1)&&rank2(posb,posa,0)==rank2(posb,posb,1))
            posa++,posb++;
        else if(posb==1)
            posa++;
        else
            posb=nxt[posb-1]+1;
        if(posb==k+1)
            stk[++ans]=posa-k,posb=nxt[posb-1]+1;
    }
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)
        cout<<stk[i]<<endl;
}
signed main(void){
    scanf("%d%d%d",&n,&k,&s);memset(num,0,sizeof(num));
    for(int i=1;i<=n;i++)
        scanf("%d",&a[0][i]),num[0][i][a[0][i]]=1;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=s;j++)
            num[0][i][j]+=num[0][i-1][j];
    for(int i=1;i<=k;i++)
        scanf("%d",&a[1][i]),num[1][i][a[1][i]]=1;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=s;j++)
            num[1][i][j]+=num[1][i-1][j];
    getnext();kmp();
    return 0;
}

---

By NeighThorn