题目描述

给出一个长度为 $N$ 的整数串 $A$，和一个长度为 $K$ 的整数串 $B$，$A$ 和 $B$ 中的元素均是不大于 $S$ 的正整数。

我们认为两个串是相等的，当两个串的长度相等，并且两个串中，对于任意的 $i$，第 $i$ 个元素在两个串中的排名是一样的。

例如：

1 2 3 5 4
8 10 23 25 24

这两个串是相等的。

现在要求在 $A$ 的所有长度等于 $B$ 的长度的子串中，有多少子串与 $B$ 串相等。

蒟蒻的die码（KMP）：

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define eb emplace_back
#define mkp(x,y) make_pair((x),(y))
#define pii pair<int,int>
#define fi first
#define se second
#define fir first
#define sec second
#define il inline
#define re register
//#define mp(x,y) make_pair((x),(y))
//#define int long long
using namespace std;
int n,m,S;
int p[555555],a[555555],b[555555];
int pree[555555],preg[555555],prel[555555];
int st[555555],top;
int last[111111];
signed main(){
	scanf("%d%d%d",&n,&m,&S);
	memset(last,-1,sizeof(last));
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;++i){
		scanf("%d",&b[i]);
		if(last[b[i]]!=-1)pree[i]=i-last[b[i]];
		else pree[i]=-1;
		last[b[i]]=i;
	}
	top=0;
	for(int i=1;i<=m;++i){
		while(top&&b[st[top]]>=b[i])--top;
		if(top)prel[i]=i-st[top];
		else prel[i]=-1;
		st[++top]=i;
	}
	top=0;
	for(int i=1;i<=m;++i){
		while(top&&b[st[top]]<=b[i])--top;
		if(top)preg[i]=i-st[top];
		else preg[i]=-1;
		st[++top]=i;
	}
	
	for(int i=1,j=0;i<m;++i){
		while(j&&!((pree[j+1]==-1||b[i+1]==b[i+1-pree[j+1]])&&(preg[j+1]==-1||b[i+1]<b[i+1-preg[j+1]])&&(prel[j+1]==-1||b[i+1]>b[i+1-prel[j+1]])))j=p[j];
		if((pree[j+1]==-1||b[i+1]==b[i+1-pree[j+1]])&&(preg[j+1]==-1||b[i+1]<b[i+1-preg[j+1]])&&(prel[j+1]==-1||b[i+1]>b[i+1-prel[j+1]]))++j;
		p[i+1]=j;
	}
	vector<int> v;
	for(int i=0,j=0;i<n;++i){
		while(j&&!((pree[j+1]==-1||a[i+1]==a[i+1-pree[j+1]])&&(preg[j+1]==-1||a[i+1]<a[i+1-preg[j+1]])&&(prel[j+1]==-1||a[i+1]>a[i+1-prel[j+1]])))j=p[j];
		if((pree[j+1]==-1||a[i+1]==a[i+1-pree[j+1]])&&(preg[j+1]==-1||a[i+1]<a[i+1-preg[j+1]])&&(prel[j+1]==-1||a[i+1]>a[i+1-prel[j+1]]))++j;
		if(j==m){
			v.eb(i+1-m+1);
			j=p[j];
		}
	}
	printf("%d\n",v.size());
	for(int i:v){
		printf("%d\n",i);
	}
	return 0;
}