【BZOJ2384】[Ceoi2011]Match
Description
作为新一轮广告大战的一部分，格丁尼亚的一家大公司准备在城市的某处设置公司的标志（logo）。公司经理决定用一些整栋的建筑来构成标志的组成部分。
v标志由不同高度的竖直条纹组成。这些条纹从左到右依次编号为1…n。标志用数字1,2,…,n的排列(s1,s2,…,sn)来描述。编号s1的条纹高度最低，编号s2的条纹第二低，…，编号sn的条纹最高。条纹的实际高度无关紧要。
v沿格丁尼亚城市的主干道共有m栋建筑，这些建筑的高度各不相同。问题是如何找出标志与建筑相匹配的所有位置。
v请帮助公司找出匹配标志的建筑序列的连续部分。若编号s1的建筑在序列中最低，编号s2的建筑在序列中第二低,…，那么这个连续的建筑序列就与标志匹配。例如，建筑高度的序列5,10,4与用编号排列(3,1,2)描述的标志相匹配，因为编号3的建筑(高度4)最低，编号1的建筑第二低，编号2的建筑最高
Input
◆第一行包含两个整数n, m (2≤n≤m≤1000000)。
第二行包含n个整数si，构成1,2,…,n的排列，1≤si≤n且si≠sj。
第三行包含m个整数hi，表示建筑的高度(1≤hi≤109,1≤i≤m)，所有的hi均不相同。
每一行的整数之间用单个空格隔开。
◆至少35分的数据，n≤5000, m≤2000
◆至少60分的数据，n≤50000, m≤200000
Output
第一行包含1 个整数k ，表示匹配的序列数目。
第二行包含k 个整数，分别为在正确匹配的每个序列中与标志编号1 的条纹相对应的第1 栋建筑的编号。这些数字按升序排列，用空格隔开。如果k=0 ，第二行为空行。
Sample Input
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9
Sample Output
2 6
题解：本题肯定是KMP，然后改一改判断相等的条件即可。但是拿什么作为判相等的条件呢？一开始想到用每个数前面第一个比它小+大的数的位置，但后来找到反例了。发现题解维护的是每个数前面所有比它小的数中，最大的数的位置（即刚好比它小的数的位置），和刚好比它大的数的位置。然后只要S中的对应位置也满足对应的关系，就认为是相等。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=1000010;
int n,m,t1,t2;
int S[maxn],T[maxn],pos[maxn],p1[maxn],p2[maxn],pre[maxn],nxt[maxn],next[maxn],ans[maxn];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd();
int i,j;
for(i=0;i<n;i++) pos[i]=rd()-1,T[pos[i]]=i;
for(i=0;i<n;i++) pre[i]=i-1,nxt[i]=(i==n-1)?-1:i+1;
for(i=0;i<m;i++) S[i]=rd();
for(i=n-1;i>=0;i--)
{
p1[i]=(pre[T[i]]==-1)?-1:(i-pos[pre[T[i]]]);
p2[i]=(nxt[T[i]]==-1)?-1:(i-pos[nxt[T[i]]]);
if(nxt[T[i]]!=-1) pre[nxt[T[i]]]=pre[T[i]];
if(pre[T[i]]!=-1) nxt[pre[T[i]]]=nxt[T[i]];
}
i=0,j=-1,next[0]=-1;
while(i<n)
{
if(j==-1||((p1[j]==-1||T[i-p1[j]]<T[i])&&(p2[j]==-1||T[i-p2[j]]>T[i]))) next[++i]=++j;
else j=next[j];
}
i=j=0;
while(i<m)
{
if(j==-1||((p1[j]==-1||S[i-p1[j]]<S[i])&&(p2[j]==-1||S[i-p2[j]]>S[i]))) i++,j++;
else j=next[j];
if(j==n)
{
ans[++ans[0]]=i-n+1,j=next[j];
}
}
printf("%d
",ans[0]);
for(i=1;i<=ans[0];i++) printf("%d%c",ans[i],i==ans[0]?'
':' ');
return 0;
}