[NFLSPC #6] 绝不能忘记的事……

Luogu

IDLGP9934

Time2000ms

Memory1024MB

DifficultyP5

字符串O2优化哈希 hashing字典树 Trie

你在电脑内记录了一条绝对不能忘记的事。但是，因为 1064 病毒的入侵，它被电脑忘记了。更可怕的是，1064 病毒似乎拥有某种跨物种传播的能力，导致你也忘记了这件事。万幸，在 1064 病毒让你和你的电脑忘记这件事之前，你及时将这件事的记录复制了 $n$ 份。但是，由于你和你的电脑在执行这件艰巨的任务的过程中受到 1064 病毒的影响忘记了很多可以忘记的事，所以你进行的操作有点奇怪。 - 首先，这件事的记录是一个长度未知（因为你已经忘记了它的长度）的字符串，称作 **记录串**。对于一份复制，你将记录串切成了三段非空的字符串 **片段**。**不同复制的场合，切割的方案不一定相同**。你暂且将这三份 **片段** 依次称作 **前面**，**中间** 和 **后面**。 - 因为电脑忘记了很多可以忘记的事，所以某些复制中的某些片段可能被忘记了。具体而言，前面有可能被替换为 `QIANMIANWANGLE`，中间有可能被替换为 `ZHONGJIANWANGLE`，后面有可能被替换为 `HOUMIANWANGLE`；在发生替换的场合，表示电脑 **完全忘记** 了这一段片段；否则，表示电脑 **完全记得** 该片段。 - 你终于想起了一件绝不能忘记的事：那就是那绝不能忘记的记录串中，**恰出现了一次** `NFLSPC#6QIDONG` 作为连续子串。除此之外，记录串中的所有其它字符都是 **小写英文字符**。并且，因为你和你的电脑始终记得这件事有多么重要，所以你在划分的时候，无意中让某一个片段恰好为 `NFLSPC#6QIDONG`；你的电脑也在每一份记录中忠实地记得这一段片段。 - 于是，你的电脑最终还记得的东西，就是：$n$ 份复制，每份复制由三段非空字符串构成，依次表示这份复制的三份片段；其中恰有一段为 `NFLSPC#6QIDONG`，另外两段要么是一串仅由小写英文字母构成的非空串，要么是对应的前面/中间/后面忘了。 - 邪恶的 1064 病毒不肯罢休，它篡改了你电脑中的信息，使得你的 $n$ 份复制不一定是自洽的。你确信 1064 病毒没有能力篡改过多的信息，并且它绝对敌不过你和你的电脑对彼此牢牢记住的 `NFLSPC#6QIDONG` 的信念。因此，你的复制仍然满足上文中所述的性质（恰有一段是 `NFLSPC#6QIDONG`，另外两段要么忘了要么是小写字母非空串）。你的目标是，寻找到初始的那绝不能忘记的记录串。这个记录串需要满足的条件是，恰出现一次 `NFLSPC#6QIDONG`，其余字符均是小写英文字符，且其匹配尽量多的复制串。 - 记录串与复制串匹配的要求是，记录串存在一种划分，使得三段划分与复制串的三段分别相同，或者复制串中这段划分忘了（此时本段划分中，记录串为任何非空英文字符串均合法）。你希望求出该记录串能匹配的最多复制串数目。至于记录串本身，你更希望将它深深地埋藏于心底，因此你不需要求出它。 > 那忘记的事只会使你的心灵更加轻盈 / 那未曾忘记的事则会让你的心灵更加坚硬 / ## Input **为了避免输入量过大，输入进行了一定程度的压缩。请务必认真阅读输入格式**。第一行一个正整数 $n$，表示记录数目。接下来 $n$ 行，每行三个非空字符串，其中第一段要么是非空小写字符串，要么是 `Q`（表示 `QIANMIANWANGLE`），要么是 `N`（表示 `NFLSPC#6QIDONG`），不存在其它可能；第二段则是非空小写字符串、`Z`（表示 `ZHONGJIANWANGLE`）、`N` 三者之一；最后一段是非空小写字符串、`H`（表示 `HOUMIANWANGLE`）、`N` 三者之一。保证三段中恰有一段为 `N`。 ## Output 一行一个整数，表示所有记录串中，能匹配的最多的复制的数目。 [samples] ## Background > 那件事…… 绝对不能忘记！ ## Note 对于所有数据，保证输入的所有字符串长度之和不超过 $10 ^ 6$。 - 子任务 1（$20$ 分）：保证复制中除了 `NFLSPC#6QIDONG` 恰出现一次以外，其它部分全部忘记。也即，输入的复制串仅可能为 `N Z H`，`Q N H`，`Q Z N` 三者之一。 - 子任务 2（$30$ 分）：保证所有复制串的 “后面” 段都是 `NFLSPC#6QIDONG`。也即，输入的复制串必然形如 `* * N`，其中 `*` 指代任意符合格式的输入。 - 子任务 3（$50$ 分）：无特殊限制。 Source：NFLSPC #6 J by Troverld

Samples

Input #1

3
N Z H
Q N H
Q Z N

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[NFLSPC #6] 绝不能忘记的事……",
    "description": {
      "content": "你在电脑内记录了一条绝对不能忘记的事。但是，因为 1064 病毒的入侵，它被电脑忘记了。更可怕的是，1064 病毒似乎拥有某种跨物种传播的能力，导致你也忘记了这件事。 万幸，在 1064 病毒让你和你的电脑忘记这件事之前，你及时将这件事的记录复制了 $n$ 份。但是，由于你和你的电脑在执行这件艰巨的任务的过程中受到 1064 病毒的影响忘记了很多可以忘记的事，所以你进行的操作有点奇怪。 - 首",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9934"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你在电脑内记录了一条绝对不能忘记的事。但是，因为 1064 病毒的入侵，它被电脑忘记了。更可怕的是，1064 病毒似乎拥有某种跨物种传播的能力，导致你也忘记了这件事。\n\n万幸，在 1064 病毒让你和你的电脑忘记这件事之前，你及时将这件事的记录复制了 $n$ 份。但是，由于你和你的电脑在执行这件艰巨的任务的过程中受到 1064 病毒的影响忘记了很多可以忘记的事，所以你进行的操作有点奇怪。\n\n- 首...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments