题意：给定一个长度为n的排列，m个数，要求在m个数中选出一段长度为n的数串，使得选出的数串与给定的排列是匹配的。匹配的定义：设给定的排列为A,选出的数串为B,要满足B[A[i]]在数串中排第i小。

 

思路：扩展KMP O(n)

 

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           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]) 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 }