题意：给你两串数字，长度分别为n和m，数字大小在[1,25]。当后一串数字每个数字的排名位置与前一串数字（任一长度为m的子串）每个数字的排名位置一致时就完全匹配，最后求哪些位置是完全匹配的。
例如：1 4 2 5 3 6 与 1 3 2 4 答案就是：1 3（第一串数字的第一个位置开始与第三个位置开始）
挺难想的一个题，我们需要使用dp的思想加前缀和进行KMP匹配
首先，两串数字串完全匹配就可以想到KMP，这样我们就只需要解决一个问题：两个数字怎样才算是“相等”（这儿并不是值一样就“相等”）。我们可以这样想，当两串数字对应位置：前面比此位置数字小的，与此位置数字相等的个数都一样，这样就一定匹配，因为这样每个数字排名位置一定相等（注意第一个数字串是子串）。
我们可以注意数字范围很小，所以可以使用前缀和记录：每个位置前面每种数字不大于这个数字大小的个数。这样求Next数组和匹配时直接使用前缀和来处理就好。
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=100010; int Next[Max],k; struct node//前i个字符中大于等于某种数字的总个数 { int num[Max][27]; }; void Init(int n,int *str,node &dp)//预处理dp { memset(dp.num[0],0,sizeof(dp.num[0])); for(int i=1;i<n;++i) { dp.num[i][0]=0; for(int j=1;j<=k;j++) { dp.num[i][j]=dp.num[i-1][j]; if(j>=str[i-1]) dp.num[i][j]=dp.num[i-1][j]+1; } } return; } int Jud(int i,int j,node &dpm,node &dpp,int *strm,int *strp)//模式串与匹配串是否匹配 { int lim=j-i; if(dpm.num[i][strm[i]]==dpp.num[j][strp[j]]-dpp.num[lim][strp[j]]&&dpm.num[i][strm[i]-1]==dpp.num[j][strp[j]-1]-dpp.num[lim][strp[j]-1])//这儿使用前缀和计算时要注意固定不大于某个值 return 1; return 0; } void GetNext(int m,int *str,node &dp)//求next数组 { Next[0]=-1; int i=-1,j=0; while(j<m) { if(i==-1||Jud(i,j,dp,dp,str,str))//当此字符前面小于等于其的都相等时就匹配 { ++i,++j; Next[j]=i; } else i=Next[i]; } return; } int strm[Max],strp[Max]; node dpm,dpp; int ans[Max],cnt; int Kmp(int n,int m)//标准模式匹配修改 { int res=0; int i=0,j=0; while(j<n) { if(i==-1||Jud(i,j,dpm,dpp,strm,strp)) { ++i,++j; } else i=Next[i]; if(i==m)//匹配成功 { ans[cnt++]=j-i+1; i=Next[i]; res++; } } return res; } int main() { int n,m; while(~scanf("%d %d %d",&n,&m,&k)) { cnt=0; for(int i=0;i<n;++i) scanf("%d",&strp[i]); for(int i=0;i<m;++i) scanf("%d",&strm[i]); Init(m,strm,dpm); GetNext(m,strm,dpm); Init(n,strp,dpp); int len=Kmp(n,m); printf("%d ",len); for(int i=0;i<len;++i) printf("%d ",ans[i]); } return 0; }