糯米

此题只有130人solved！也算小牛题了，刚开始看到的时候，打算不做了的，但后来想了一下，发现有一点点思路。
经过好几个小时的奋战，居然做出来了！那感觉非常爽！

思路：

首先此题的变态之处是，要求比较的是排名，就不是单纯的字符串匹配了。
如果每次都重新求排名然后跟pattern比较，复杂度 O(NK)，八成会超时。
关键是：
一，不能每次都重新求排名
二，不能逐个逐个的和pattern做比较
看来也只有动态规划或者hash能满足这种需求。

对于前 K 个数字，求出一个初始的 hash 值。
对于后 N - K 个数字，不断的把大小为 K 的窗口向后一格格滑动，比如 [1, 5] -> [2, 6] -> [3, 7]。
hash 值随之更新，如果和pattern的hash值一致，那么当前的区间就是一个答案了。

一开始，想到的hash函数是，
hash = rank[1] * a[1] + rank[2] * a[2] + ... rank[K] * a[K]
其中：
所有数字的类型都为32bit无符号整数
数组 a 为等差数列
rank 为着窗口内的排名，跟 pattern 的格式一样，长度为 K。

由于 S <= 25 ，所以可以把数值相同的元素保存在一起，因它们的rank值也是一样的，
那 hash 函数就变成了这样子：
hash = 1 * (a[1] + a[3] ...) + 2 * (a[2] + a[7] + ...) + ...
其中 rank[1] = rank[3] = 1，rank[2] = rank[7] = 2。。。
可以维护大小为 S 的数组 pos 、rank_val：
pos[i] = { 元素 i 出现的位置对应的 hash 值，如果没出现过，则为 0 }
pos[1] = a[1] + a[3] + ...   
pos[2] = a[2] + a[7] + ...
。。。
rank_val[i] = { 元素 i 对应的 rank }
rank_avl[1] = 1
rank_avl[2] = 2
。。。
因而：
hash = rank_val[1] * pos[1] + rank_val[2]  * pos[2] + ...  + rank_val[K] * pos[K]

窗口每次滑动一格的时候，都要先增加一个元素，然后减掉一个元素。
再维护一个大小为 S 的数组 cnt：
cnt[i] = { 元素 i 在窗口中出现的次数 }
这样，每次增删元素的时候，就很容易得出 rank_val 数组的内容了，就跟基数排序一个原理。

增加元素 i 的时候，首先增加 pos[i], cnt[i] 的值，然后扫描一遍 cnt 更新 rank_val 的值。
删除元素的情况类似。

窗口向后移动了一格之后：
pos[2] = a[2] + a[7]
应该变化为
pos[2] = a[1] + a[6]
这时候，由于 a 是等差数列，假设它的公差为 d，那么只需要 pos[2] -= cnt[2] * d 就能在 O(1) 时间内完成这种“移动”操作了！

因此，在窗口移动一格的过程中，步骤为：
一，增加窗口末尾后的第一个元素
二，删除窗口开头元素
三，“移动”窗口中所有元素
四，与 pattern 比较 hash 值

总的时间复杂度是 O(NS)。

后来，发现有的数据过不了，hash 冲突了，又将 hash 函数变化了一下：
hash = rank_val[1]^5 * pos[1] + rank_val[1]^5 * pos[2] ... rank_val[K]^5 * pos[K]
发现求到 4 次方的时候貌似还是有冲突。。。
到 5 次方的时候就 AC 了！

代码跑了 350 ms

代码：