http://poj.org/problem?id=3461
KMP这里讲的不错next的求法值得借鉴 http://blog.sina.com.cn/s/blog_70bab9230101g0qv.html
这道题要用到KMP，基于邝斌牌模板，复杂度O(M+N)
一开始T了，用了后缀数组，复杂度O(Nlog2n)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
#define N 100010
char s[N * ], 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[]=-;
i=;
while(i<m)
{
while(-!=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[];
int KMP_Count(char x[],int m,char y[],int n)
{
//x是模式串，y是主串
int i,j;
int ans=;
//preKMP(x,m,next);
kmp_pre(x,m,next);
i=j=;
while(i<n)
{
while(-!=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\n", ans);
}
return ;
}
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int n,k,m,number;
int rank[],tmp[],sa[];
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]:-;
int rj=j+k<=n?rank[i+k]:-;
return ri<rj;
}
}
void construct_sa(string s,int *sa)
{
n=s.length();
for(int i=;i<=n;i++)
{
sa[i]=i;
rank[i]=i<n?s[i]:-;
}
for(k=;k<=m;k*=) //这里的k是递归到长度为k的串
{
sort(sa,sa+n+,common_sa);
tmp[sa[]]=;
for(int i=;i<=n;i++)
{
tmp[sa[i]]=tmp[sa[i-]]+(common_sa(sa[i-],sa[i])?:);
}
for(int i=;i<=n;i++)
{
rank[i]=tmp[i];
}
}
}
bool contain(string s,int *sa,string t)
{
int a=,b=s.length();
while(b-a>)
{
int c=(a+b)/;
if(s.compare(sa[c],t.length(),t)<) a=c;
else b=c;
}
return s.compare(sa[b],t.length(),t)==;
} 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<<""<<endl;
else
{
char c=mode[];
for(int i=;i<n;i++)
{
if(donser[i]==c)
{
int y=rank[i];number=;
for(int j=i;j<n;j++)
{
if(rank[j]==y) number++;
}
break;
}
}
cout<<number<<endl;
}
}
return ;
}
T掉的 后缀数组
后缀数组这里也有值得说的
rank数组对字串长度做1 2 4 8这样的增长式划分，划分的最大长度可以直接定为匹配串的长度，
这样根据rank数组的值和位置就能知道相同的串个数了。