题意：给定一个长度为n的排列，m个数，要求在m个数中选出一段长度为n的数串，使得选出的数串与给定的排列是匹配的。匹配的定义：设给定的排列为A,选出的数串为B,要满足B[A[i]]在数串中排第i小。
思路：扩展KMP O(n)
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<cmath>
5 using namespace std;
6 #define MAXN 1000000+100
7 int b[MAXN],a[MAXN],p[MAXN],home[MAXN],behind[MAXN],front[MAXN],big[MAXN],small[MAXN],ans[MAXN];
8 int n,m,top;
9 void make_big_small()
10 {
11 int i;
12 int x,y;
13 for(i=n;i>0;i--)
14 {
15 small[i]=home[front[a[i]]];
16 big[i]=home[behind[a[i]]];
17 x=front[a[i]]; y=behind[a[i]];
18 behind[x]=y; front[y]=x;
19 }
20 }
21
22 bool equal(int a[],int i,int j)
23 {
24 if(big[i]!=-1&&a[j+big[i]-i]<a[j])
25 return 0;
26 if(small[i]!=-1&&a[j+small[i]-i]>a[j])
27 return 0;
28 return 1;
29 }
30
31 void make_p()
32 {
33 int i,k;
34 p[1]=k=0;
35 for(i=2;i<=n;i++)
36 {
37 while(k>0&&!equal(a,k+1,i)) k=p[k];
38 if(equal(a,k+1,i)) k++;
39 p[i]=k;
40 }
41 }
42
43 int main()
44 {
45 freopen("mat.in","r",stdin);
46 freopen("mat.out","w",stdout);
47 scanf("%d%d",&n,&m);
48 int i,k=0,x;
49 for(i=1;i<=n;i++)
50 {
51 scanf("%d",&x); a[x]=i; home[i]=x;
52 behind[i]=i+1; front[i]=i-1;
53 }
54 for(i=1;i<=m;i++) scanf("%d",b+i);
55 home[n+1]=-1; home[0]=-1;
56 make_big_small();
57 make_p();
58 for(i=1;i<=m;i++)
59 {
60 while(k>0&&!equal(b,k+1,i)) k=p[k];
61 if(equal(b,k+1,i)) k++;
62 if(k==n) ans[++top]=i-n+1, k=p[k];
63 }
64 printf("%d\n",top);
65 for(i=1;i<=top;i++) printf("%d ",ans[i]);
66 printf("\n");
67 return 0;
68 }