这题的瓶颈在于数字的大小位置是不确定的，而且题目要求只要对应位置的数字的大小关系一样就可以称之为匹配
如果说把它们弄成确定的字母什么的就好做了吧？！（神马？如果连这个你都不会你就出去吧！）
那么我们只要确定一个数字在一定区域内的大小排位就可以了！！
怎么确定呢？
我们弄个数组比如s吧，s[i][j]表示的是到第i位位置j这个数字出现过多少次
那么比如我要确定i-j+1～i-1这个区域内比a[i]小的数字的个数，只要用s[i-j+1][1]加到s[i-j+1][a[i]-1]就可以确定在1～i-j+1这个区域内比a[i]小的数字的个数
然后用s[i-1][1]加到s[i-1][a[i]-1]就可以确定1～i-1这个区域内比a[i]小的数字的个数，拿后面的那个和减掉前面的那个和，就可以确定a[i]这个大小位置，但单单是判断了比它小的数字的个数是不够的，还要比较到当前为止的跟a[i]一样大的数字的个数，这个也很好搞吧？然后通过这两条信息（一个是比它小，一个是一样大）可以唯一确定一个数字在一定区域内的排位情况，相当于是给它hash了一下，变成了一个确定的值，接着kmp就可以了

还有神牛用树状数组、后缀数组神马东东的，只能膜拜了……我总是挑简单的程序打的，代码不是很长，大概也就50来行吧

• Re:不会的童鞋进来看，神牛勿进 (576) shaynelq 2013-03-06 20:20:21