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<<'\n';

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\n", 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;

}