很久之前做的一题，忽然想起来，依然觉得思路巧妙。
//这道题，确实是一道好题。但如何应用KMP，确实大大超出了意料中。 //这道题匹配的是某元素在子串中的名次，也就是在子串中排第几小。我想了整整一天，才想到一个较好 //的方法来确定在子串中的位置，本来以为可以用这个来暴力枚举再加剪枝可以过，但没想到。。TLE //代码是转的，算法也是看过别人的才懂。 //好吧，看过别人的解题，写的代码不难，算法特别难想。首先统计在位置I的元素之前，比该元素小的个数 //以及和该元素相等的个数，这个我用暴力枚举来预处理，也有用树状数组的，但我看不懂。然后重新修改 //匹配的定义：假设前N-1个元素匹配，则第N个元素匹配的条件是该元素之前的（当然必须是在子串范围内） //小于与等于该元素的个数都分别相等。我试图否定它，但总感觉是显而易见的，可我没想到。接下来就可以 //据此来求NEXT函数了。在求NEXT时，必须注意是要求N-1个元素中小于与等于N元素的个数分别相等。 //我想做一次事后诸葛亮（虽然本人不是什么牛人），总结一下： //我觉得，以后遇到配匹模式串的题应该都可以用KMP来解题，真心觉得KMP是十分的一个算法。但在应用NEXT //函数时，应适当改一下定义，怎么改呢？我认为，要求某位置的NEXT的值，应该首先满足的条件时，该位置 //之前的字符或数已匹配，所以，应当先假设前N个元素匹配，再给出N+1个元素匹配的条件，且应该是无须 //理会N+1之后的影响的。这样就可以进行KMP了。 #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; int n,k,s; struct TT { int len; int num[111111]; int low[111111][33],equ[111111][33]; } t,p; void init(TT &tmp) { for(int i =1;i<=tmp.len;i++) { for(int j = 1;j<=s;j++) { tmp.low[i][j] = tmp.low[i-1][j] + (tmp.num[i] < j ? 1 : 0); tmp.equ[i][j] = tmp.equ[i-1][j] + (tmp.num[i] == j ? 1 : 0); } } } int fail[25555]; int check(TT &a,TT &b,int i,int j) { if(a.low[i][a.num[i]] - a.low[i - j][a.num[i]] == b.low[j][b.num[j]] && a.equ[i][a.num[i]] - a.equ[i - j][a.num[i]] == b.equ[j][b.num[j]]) return 1; return 0; } void get_fail() { fail[1] = 0; int j = 0; for(int i = 2;i<=k;i++) { if(j >= 1 && !check(p,p,i,j+1) ) j = fail[j]; if(check(p,p,i,j+1)) j++; fail[i] = j; } } vector <int> ans; void kmp() { ans.clear(); get_fail(); int j = 0; for(int i = 1;i<=n;i++) { while(j >= 1 && !check(t,p,i,j+1)) j = fail[j]; if(check(t,p,i,j+1)) j++; if(j == k) { ans.push_back(i-k+1); j = fail[j]; } } } int main() { while(~scanf("%d%d%d",&n,&k,&s)) { for(int i = 1;i<=n;i++) scanf("%d",&t.num[i]); for(int i = 1;i<=k;i++) scanf("%d",&p.num[i]); t.len = n; p.len = k; init(t); init(p); kmp(); printf("%d ",ans.size()); for(int i = 0;i<ans.size();i++) printf("%d ",ans[i]); } return 0; }