参考http://www.cppblog.com/zxb/archive/2010/10/06/128782.aspx?opt=admin
明天晚上机器人机考,后天英语和机器人的笔试,求RP...
#include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<queue> #include<fstream> using namespace std; int occur[26],low[25005],high[25005]; int P[25005],T[100005],suffix[25005],N,K,S; queue<int> s; bool match(int *P,int *T,int q,int b) { if(occur[P[q]]!=-1&&occur[P[q]]<q) { int t=occur[P[q]]; if(T[b]==T[b-(q-t)]) return 1; else return 0; } else { if(low[q]!=-1) { int t=low[q]; if(T[b]<=T[b-(q-t)]) return 0; } if(high[q]!=-1) { int t=high[q]; if(T[b]>=T[b-(q-t)]) return 0; } return 1; } } void pre() { int q=0,i,j; memset(occur,-1,sizeof(occur)); memset(low,-1,sizeof(low)); memset(high,-1,sizeof(high)); suffix[0]=0; occur[P[0]]=0; for(i=1;i<K;++i) { while(q>0&&!match(P,P,q,i)) q=suffix[q-1]; if(match(P,P,q,i)) q++; suffix[i]=q; for(j=P[i]-1;j>0;--j) if(occur[j]!=-1) { low[i]=occur[j]; break; } for(j=P[i]+1;j<=S;++j) if(occur[j]!=-1) { high[i]=occur[j]; break; } if(occur[P[i]]==-1) occur[P[i]]=i; } // cout<<"prepare complete"<<endl; return ; } void KMP() { int i,q=0; while(!s.empty()) s.pop(); pre(); for(i=0;i<N;++i) { while(q>0&&!match(P,T,q,i)) q=suffix[q-1]; if(match(P,T,q,i)) q++; if(q==K) { s.push(i-K+1); q=suffix[K-1]; } } return ; } int main() { int i,num; // ifstream fin; // fin.open("data.txt"); while(scanf("%d %d %d",&N,&K,&S)!=EOF) // while(fin>>N>>K>>S) { for(i=0;i<N;++i) scanf("%d",T+i); // fin>>T[i]; for(i=0;i<K;++i) scanf("%d",P+i); // fin>>P[i]; KMP(); num=s.size(); printf("%d\n",num); while(!s.empty()) { printf("%d\n",s.front()+1); s.pop(); } } // system("pause"); return 0; }