#329. 问题3:不适的曲调(moosick)

问题3:不适的曲调(moosick)

题目描述

所有人都知道奶牛喜欢听所有种类的音乐。几乎所有种类,也就意味着,伟大的奶牛作曲家 Wolfgang Amadeus Moozart 有次发现了一个特殊的和弦可以让奶牛感到不适。这个和弦就是著名的反刍动物第七和弦,因此所有的奶牛音乐作曲家都会特意回避它。

Farmer John 并不了解奶牛作曲史的细节,他打算在牛棚大声的播放他喜欢的音乐。你的任务就是在这首歌中识别出所有的反刍动物第七和弦,从而评估它会让奶牛感到有多不适。

FJ 播放的这首歌由一系列的 NN1N200001 ≤ N ≤ 20000 )个音符组成,每个音符表示成一个范围在 [1,88][1, 88] 内的整数。反刍动物第七和弦可以用 CC1C101 ≤ C ≤ 10 )个独特的音符序列表示,每个音符也是范围在 [1,88][1, 88] 内的整数。然而,即便这些音符是变调的(同时增加或者减少一个常数),或者重排的,它依旧是反刍动物第七和弦!例如,如果 4,6,74, 6, 7 是反刍动物第七和弦,那么 3,5,63, 5, 6 (同时减 11 并重排), 6,8,96, 8, 9 (同时加 22 ), 6,4,76, 4, 7 (重排), 5,3,65, 3, 6 (变调并重排)都是反刍动物第七和弦。

一个反刍动物第七和弦就是满足上述标准的长为 CC 的连续音符序列。因此它可以用在歌曲中的起始位置进行唯一标识。请求出所有反刍动物第七和弦在歌曲中出现的起始位置。

输入格式(文件名:moosick.in)

11 行:一个整数 NN

21+N2 \dots 1 + N 行: FJ 的歌曲的 NN 个音符,每个音符一行。

2+N2 + N 行:一个整数 CC

3+N2+N+C3 + N \dots 2 + N + C 行:反刍动物第七和弦的 CC 个音符样例。所有的变调或者重排都还是反刍动物第七和弦。

输出格式(文件名:moosick.out)

11 行:一个数量 KK ,表示 FJ 的歌中反刍动物第七和弦出现的次数。注意不同的和弦段是可以有重叠部分的。

21+K2 \dots 1 + K 行:每行一个反刍动物第七和弦的起始下标( 11 是 FJ 的歌中的第一个音符, NN 是最后一个)。下标需要按照升序排列。

输入样例

6
1
8
5
7
9
10
3
4
6
7

输出样例

2
2
4

样例解释

FJ 的歌是 1,8,5,7,9,101, 8, 5, 7, 9, 10 ,一个反刍动物第七和弦是 4,6,74, 6, 7 的变调或者重排。

FJ 的歌中出现了两次反刍动物第七和弦(并且这两次出现有一个音符的重叠)。第一个是起点为 228,5,78, 5, 7(变调 +1+1 并重排),第二个是起点为 447,9,107, 9, 10(变调 +3+3 )。