POJ 3461 Oulipo(模式串在主串中出现次数 可重叠)

Oulipo

【题目链接】Oulipo

【题目类型】KMP

&题意：

给你两个字符串p和s，求出p在s中出现的次数。

&题解：

kmpC函数就是解题的,其中也就j=nex[j]难理解一些,j=nex[j]就代表对照的开始,如果j=nex[j]的值是4,就代表从第4个位置开始比较,正如这句话上面的那个j++,你都匹配上了,所以就会有j++,之后便会j大于等于匹配串的长度,这就代表找到了一个和匹配串一样的串,所以ans++,之后再去找该从哪个位置开始匹配

【时间复杂度】(O(n+m))

&代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i--)
#define PU(x) cout<<#x<<'
';
const int maxn = 1e6 + 9 ;
int nex[maxn],n,ans[maxn];
char x[maxn],y[maxn];
void kmpN(char* x,int len) {
	int i=0,j=nex[0]=-1;
	while(i<len) {
		while(j!=-1&&x[i]!=x[j]) {
			j=nex[j];
		}
		nex[++i]=++j;
	}
}
int kmpC(char x[],int m,char y[],int n) {
	int i=0,j=0,ans=0;
	while(i<n) {
		while(j!=-1&&y[i]!=x[j]) j=nex[j];
		i++; j++;
		if(j>=m) {
			ans++;
			j=nex[j];
			// 换成这个就是不重复的了,因为j没有记录以前的长度
			// 所以上面的j++就得重新加,就代表j>=m的条件就越远了
			// j=0;
		}
	}
	return ans;
}
void Solve() {
	scanf("%s",x);
	scanf("%s",y);
	int m=strlen(x);
	n=strlen(y);
	kmpN(x,m);
	int tt=kmpC(x,m,y,n);
	printf("%d
", tt);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin),freopen("1.out","w",stdout);
#endif
//iostream::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T; cin>>T; while(T--)
		Solve();
	return 0;
}