字符串专题：KMP POJ 3561

KMP这里讲的不错next的求法值得借鉴 http://blog.sina.com.cn/s/blog_70bab9230101g0qv.html

这道题要用到KMP，基于邝斌牌模板，复杂度O(M+N)

一开始T了，用了后缀数组，复杂度O(Nlog²n)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
#define N 100010
char s[N * 10], p[N];
/*
* next[]的含义：x[i-next[i]...i-1]=x[0...next[i]-1]
* next[i]为满足x[i-z...i-1]=x[0...z-1]的最大z值（就是x的自身匹配）
*/
void kmp_pre(char x[],int m,int next[])
{
    int i,j;
    j=next[0]=-1;
    i=0;
    while(i<m)
    {
        while(-1!=j && x[i]!=x[j])j=next[j];
        next[++i]=++j;
    }
}
/*
* kmpNext[]的意思：next'[i]=next[next[...[next[i]]]] (直到next'[i]<0或者x[next'[i]]!=x[i])
* 这样的预处理可以快一些
*/
/*void preKMP(char x[],int m,int kmpNext[])
{
    int i,j;
    j=kmpNext[0]=-1;
    i=0;
    while(i<m)
    {
        while(-1!=j && x[i]!=x[j])j=kmpNext[j];
        if(x[++i]==x[++j])kmpNext[i]=kmpNext[j];
        else kmpNext[i]=j;
    }
}*/
/*
* 返回x在y中出现的次数，可以重叠
*/
int next[10010];
int KMP_Count(char x[],int m,char y[],int n)
{
    //x是模式串，y是主串
    int i,j;
    int ans=0;
    //preKMP(x,m,next);
    kmp_pre(x,m,next);
    i=j=0;
    while(i<n)
    {
        while(-1!=j && y[i]!=x[j])j=next[j];
        i++;
        j++;
        if(j>=m)
        {
            ans++;
            j=next[j];
        }
    }
    return ans;
}
int main()
{
    int ncase;
    int ans;
    scanf("%d", &ncase);
    while(ncase--)
    {
        scanf("%s%s", p, s);
        int lens = strlen(s);
        int lenp = strlen(p);
        ans=KMP_Count(p,lenp,s,lens);
        printf("%d
", ans);
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int n,k,m,number;
int rank[1000005],tmp[1000005],sa[1000005];
bool common_sa(int i,int j)
{
    if(rank[i]!=rank[j]) return rank[i]<rank[j];
    else
    {
        int ri=i+k<=n?rank[i+k]:-1;
        int rj=j+k<=n?rank[i+k]:-1;
        return ri<rj;
    }
}
void construct_sa(string s,int *sa)
{
    n=s.length();
    for(int i=0;i<=n;i++)
    {
        sa[i]=i;
        rank[i]=i<n?s[i]:-1;
    }
    for(k=1;k<=m;k*=2) //这里的k是递归到长度为k的串
    {
        sort(sa,sa+n+1,common_sa);
        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++)
        {
            tmp[sa[i]]=tmp[sa[i-1]]+(common_sa(sa[i-1],sa[i])?1:0);
        }
        for(int i=0;i<=n;i++)
        {
            rank[i]=tmp[i];
        }
    }
}
bool contain(string s,int *sa,string t)
{
    int a=0,b=s.length();
    while(b-a>1)
    {
        int c=(a+b)/2;
        if(s.compare(sa[c],t.length(),t)<0) a=c;
        else b=c;
    }
    return s.compare(sa[b],t.length(),t)==0;
}

int main()
{
    string mode,donser;
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    while(cin>>mode>>donser)
    {
        n=donser.size();
        m=mode.size();
        construct_sa(donser,sa);
        if(!contain(donser,sa,mode)) cout<<"0"<<endl;
        else
        {
            char c=mode[0];
            for(int i=0;i<n;i++)
            {
                if(donser[i]==c)
                {
                    int y=rank[i];number=0;
                    for(int j=i;j<n;j++)
                    {
                        if(rank[j]==y) number++;
                    }
                    break;
                }
            }
            cout<<number<<endl;
        }
    }
    return 0;
}

T掉的后缀数组

后缀数组这里也有值得说的

rank数组对字串长度做1 2 4 8这样的增长式划分，划分的最大长度可以直接定为匹配串的长度，

这样根据rank数组的值和位置就能知道相同的串个数了。