[文章目录]
Description
给出一个长度为N的整数串A，和一个长度为K（K<=N）的整数串B，A和B中的元素均是不大于S的正整数，我们认为两个串是相等的，当两个串的长度相当，并且两个串中，对于任意的i，第i个元素在两个串中的排名是一样的。 例如： 1 2 3 5 4 8 10 23 25 24 这两个串是相等的。求在A的所有长度=B的长度的子串中，有多少子串与B串相等。n<=5*10^5 s<=10^4
特殊意义下的kmp。
那么只需要将kmp的条件改变，考虑对于当前那些东西可以决定当前元素可以继续匹配【之前的排名已经匹配】，即当前元素的什么可以确定当前元素的排名。
由于之前的串已经匹配，那么当前元素只需要小于模式串中比当前权值刚好大的位置上的权值，大于模式串中比当前权值刚好小的位置上的权值，等于模式串中等于当前权值的位置上的权值即可。
由于排名是相对位置的大小比较，那么我们可以记录当前位置前面所需位置与其的距离，匹配的时候直接比较该相对位置上的权值大小即可。
加上双向链表维护权值，来优化预处理中寻找当前权值前面的前驱和后继的位置即可达到线性时间复杂度。
#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 501000
using namespace std;
char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
void read(int &x)
{
x=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
}
stack<int>z[11000];
int n,m,s,a[N],h[N],pre[11000],nxt[N],p1[N],p2[N],p3[N];
int main()
{
read(m); read(n); read(s); int i;
for(i=0;i<m;++i) read(h[i]);
for(i=0;i<n;++i) read(a[i]);
for(i=0;i<n;++i)
{
p1[i]= z[a[i]].empty() ? -1 : i-z[a[i]].top();
z[a[i]].push(i);
}
int now=-1;
for(i=1;i<=s;++i) if(!z[i].empty())
{
pre[i]=now; nxt[i]=-1;
if(now!=-1) nxt[now]=i;
now=i;
}
for(i=n-1;~i;--i)
{
p2[i]=(pre[a[i]]==-1) ? -1 : i-z[pre[a[i]]].top();
p3[i]=(nxt[a[i]]==-1) ? -1 : i-z[nxt[a[i]]].top();
z[a[i]].pop();
if(z[a[i]].empty())
{
if(pre[a[i]]!=-1) nxt[pre[a[i]]]=nxt[a[i]];
if(nxt[a[i]]!=-1) pre[nxt[a[i]]]=pre[a[i]];
}
}
i=0; int j=-1; nxt[0]=-1;
while(i<n)
{
if(j==-1||((p1[j]==-1||a[i-p1[j]]==a[i])&&(p2[j]==-1||a[i-p2[j]]<a[i])&&(p3[j]==-1||a[i-p3[j]]>a[i])))
nxt[++i]=++j;
else j=nxt[j];
}
memset(a,0,sizeof a);
j=0,i=0;
while(j<m)
{
if(i==-1 || ((p1[i]==-1||h[j-p1[i]]==h[j]) && (p2[i]==-1||h[j-p2[i]]<h[j]) && (p3[i]==-1||h[j-p3[i]]>h[j]) ) )
++i,++j;
else i=nxt[i];
if(i==n)
{
a[++a[0]]=j-n+1;
i=nxt[i];
}
}
printf("%d\n",a[0]);
for(i=1;i<=a[0];++i)
printf("%d\n",a[i]);
return 0;
}