BZOJ2372 music

Luogu

IDLGP10634

Time1000ms

Memory512MB

DifficultyP5

字符串O2优化哈希 hashingKMP 算法

最近 A、B 两国发生了一场战争。dick 作为 A 国的军事总指挥，最近非常头痛于己方的情报问题。因为 B 国最近雇佣了 Easy 这一位密码专家来给他们的所有通讯加密。 Easy 非常喜欢唱歌，于是他决定将所有的信号都变成旋律储存起来，比如说 $11556654433221$ 就可能是一段加过密的音符，我们用一个等长度的序列来表示它，就变成了 $1,1,5,5,6,6,\dots$。为了增加密码的保密性，他把加密的乐谱又调整了一下，把某些音调改变了，将原序列 $A$ 变成 $B$，有 $|A|=|B|$，且对于 $a_i=a_j$ 有 $b_i=b_j$，对于 $a_i<a_j$ 有 $b_i<b_j$，对于 $a_i>a_j$ 有 $b_i>b_j$。例如：`11221` 和 `55775` 就可能代表了同一段音符。最近，dick 截获了一段信号，这段信号中可能包含了某些重要信息。根据以往的经验，dick 已经知道了某些旋律所代表的意义。于是 dick 想知道，对于一段已知的旋律，能不能判断它是否在这段截获的旋律中出现？如果出现了，能否找出它出现的次数及位置呢？「任务」判断给定旋律在截获旋律中出现的次数及位置。 ## Input 第一行三个正整数 $n,m,s$，$n$ 是截获旋律的长度，$m$ 是已知旋律的长度，所有的旋律都是 $1\sim s(s\leq 25)$ 的正整数。接下来 $n$ 行，每行一个整数描述截获的旋律 $A$；接下来 $m$ 行，每行一个整数描述已知的旋律 $B$； ## Output 第一行一个整数 $t$ 表示出现的次数。然后 $t$ 行，按照从小到大给出出现时的起始位置 $p$，即：$A[p\dots p+m-1]$ 等价于 $B$。 [samples] ## Note 对于所有数据，保证 $1\leq n \leq 10^5$，$1\leq m \leq 25000$。

Samples

Input #1

Output #1

1
3

API Response (JSON)

{
  "problem": {
    "name": "BZOJ2372 music",
    "description": {
      "content": "最近 A、B 两国发生了一场战争。dick 作为 A 国的军事总指挥，最近非常头痛于己方的情报问题。因为 B 国最近雇佣了 Easy 这一位密码专家来给他们的所有通讯加密。 Easy 非常喜欢唱歌，于是他决定将所有的信号都变成旋律储存起来，比如说 $11556654433221$ 就可能是一段加过密的音符，我们用一个等长度的序列来表示它，就变成了 $1,1,5,5,6,6,\\dots$。为了增加",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10634"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "最近 A、B 两国发生了一场战争。dick 作为 A 国的军事总指挥，最近非常头痛于己方的情报问题。因为 B 国最近雇佣了 Easy 这一位密码专家来给他们的所有通讯加密。\n\nEasy 非常喜欢唱歌，于是他决定将所有的信号都变成旋律储存起来，比如说 $11556654433221$ 就可能是一段加过密的音符，我们用一个等长度的序列来表示它，就变成了 $1,1,5,5,6,6,\\dots$。为了增加...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments