此題只有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
代碼：
#include <stdio.h>
#define MAX_K 25032
#define MAX_N 100032
#define MAX_S 32
#define HASH_START 0xdead
#define HASH_INC 0xbeef
struct spot_node 
{
unsigned int cnt, rank, sum;
};
struct seq_node {
struct spot_node spot[MAX_S];
unsigned int hash;
};
struct seq_node ptn, seq;
unsigned int N, K, S;
unsigned int hash_idx[MAX_K], in[MAX_N + MAX_K], rank_pow[MAX_S];
unsigned int ans[MAX_N], ans_cnt;
#define always_inline __inline
always_inline unsigned int rank_hash(unsigned int i)
{
return rank_pow[i];
}
always_inline void seq_insert(struct seq_node *s, unsigned int val)
{
struct spot_node *t;
t = &s->spot[val];
t->cnt++;
t->sum += hash_idx[K + 1];
s->hash += hash_idx[K + 1] * rank_hash(t->rank);
if (t->cnt != 1)
return ;
for (val++; val <= S; val++) {
t = &s->spot[val];
s->hash += t->sum * (rank_hash(t->rank + 1) - rank_hash(t->rank));
t->rank++;
}
}
always_inline void seq_delete(struct seq_node *s, unsigned int val)
{
struct spot_node *t;
t = &s->spot[val];
t->cnt--;
t->sum -= hash_idx[1];
s->hash -= hash_idx[1] * rank_hash(t->rank);
if (t->cnt != 0)
return ;
for (val++; val <= S; val++) {
t = &s->spot[val];
s->hash -= t->sum * (rank_hash(t->rank) - rank_hash(t->rank - 1));
t->rank--;
}
}
always_inline void seq_advance(struct seq_node *s)
{
unsigned int i;
struct spot_node *t;
for (i = 1; i <= S; i++) {
t = &s->spot[i];
s->hash -= t->cnt * rank_hash(t->rank) * HASH_INC;
t->sum -= t->cnt * HASH_INC;
}
}
always_inline void seq_init(struct seq_node *s, unsigned int *arr)
{
unsigned int i, r;
struct spot_node *t;
s->hash = 0;
for (i = 1; i <= K; i++) {
t = &s->spot[*arr++];
t->sum += hash_idx[i];
t->cnt++;
}
for (i = r = 1; i <= S; i++) {
t = &s->spot[i];
t->rank = r;
if (t->cnt) {
s->hash += rank_hash(t->rank) * t->sum;
r++;
}
}
}
int main()
{
unsigned int i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &N, &K, &S);
for (i = 0; i < N + K; i++)
scanf("%d", &in[i]);
hash_idx[1] = HASH_START;
for (i = 2; i <= K + 1; i++)
hash_idx[i] = hash_idx[i - 1] + HASH_INC;
for (i = 1; i <= S; i++)
rank_pow[i] = i * i * i * i * i;
seq_init(&ptn, in + N);
seq_init(&seq, in);
for (i = K; ; i++) {
if (seq.hash == ptn.hash)
ans[ans_cnt++] = i - K + 1;
if (i == N)
break;
seq_insert(&seq, in[i]);
seq_delete(&seq, in[i - K]);
seq_advance(&seq);
}
printf("%d\n", ans_cnt);
for (i = 0; i < ans_cnt; i++)
printf("%d\n", ans[i]);
return 0;
}