POJ-3461 Oulipo(KMP,模式串在主串中出现次数)

  题意:给你两个字符串p和s,求出p在s中出现的次数。

  显然,我们要先把模式串放到前面,之后主串放后面,中间隔开,这样就可以根据前缀数组的性质来求了。

  我先想直接把p接到s前面,之后求Next数组对strlen(p)取余==0的就可以,之后WA。最后发现A AASSAAS的时候有bug,只有又想到在p和s中间加个不可能出现的字符'$'就可以了,接着就A了。

#include <bits/stdc++.h>
using namespace std; const int INF=0x3f3f3f3f;
typedef long long ll;
#define PI(A) printf("%d\n",A)
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++)
#define reRep(i,a,b) for(int i=(a);i>=(b);i--)
const double EPS= 1e- ; /* ///////////////////////// C o d i n g S p a c e ///////////////////////// */ const int MAXN= + + ; void kmp_pre(int 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;
}
}
int Next[MAXN],inp[MAXN];
int N,M;
char str1[+],str2[+];
int main()
{ int o;
SI(o);
while(o--)
{
scanf("%s",str1);
scanf("%s",str2);
N=strlen(str1),M=strlen(str2);
str1[N]='$';
N++;
for (int i=;i<N;i++)
inp[i]=str1[i];
for (int i=N;i<N+M;i++)
inp[i]=str2[i-N];
kmp_pre(inp,N+M,Next);
int ans=;
Rep(i,,N+M) if (Next[i]%(N-)==&&Next[i]!=) ans++;
PI(ans);
} return ;
}
上一篇:Hadoop之RPC简单使用(远程过程调用协议)


下一篇:使用SOCKET实现TCP/IP协议的通讯