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