[NFLSPC #6] 啊，忘记了。

Luogu

IDLGP9935

Time1000ms

Memory1024MB

DifficultyP6

字符串线段树O2优化哈希 hashing虚树字典树 TrieAC 自动机

你在你的电脑上发现了 $n$ 份文本。冥冥之中，你没来由地感觉这似乎全都是一份记录的复制。 - 首先，原始记录是一个长度未知（甚至可以为空）的字符串，称作 **记录串**。对于一份复制，其将记录串切成了三段 **可以为空** 的字符串 **片段**。**每份复制中切割方案不保证相同**。你暂且将这三份 **片段** 依次称作 **前面**，**中间** 和 **后面**。 - 某些复制中的某些片段可能被忘记了。具体而言，前面有可能被替换为 `QIANMIANWANGLE`，中间有可能被替换为 `ZHONGJIANWANGLE`，后面有可能被替换为 `HOUMIANWANGLE`；在发生替换的场合，表示这一段片段被 **完全遗忘** 了；否则，表示该片段被 **完整保存**。 - 你有一种预感，记录串中的所有字符都是 **小写英文字符**。 - $n$ 份复制不一定自洽。你的目标是，寻找初始的记录串。这个记录串需要满足所有字符均是小写英文字符。你希望其匹配尽量多的复制串。 - 记录串与复制串匹配的要求是，存在记录串的一种划分，使得其中记录串的三段与复制串的三段分别相同，或者复制串中这段划分忘了（此时本段划分中，记录串为任何可以为空的小写英文字符串均合法）。你希望求出该记录串能匹配的最多复制串数目。**至于记录串本身，你感觉它并不是很重要，所以你不需要求出它**。 > / 我，毋畏遗忘 / ## Input **为了避免输入过大，输入进行了一定程度的压缩。请务必认真阅读输入格式**。第一行一个正整数 $n$，表示记录数目。接下来 $n$ 行，每行三个非空字符串，其中第一段要么是非空小写字符串，要么是 `Q`（表示 `QIANMIANWANGLE`），要么是 `E` 表示这是一段空串（因为空串不可见所以选取 `E` 作为占位符），不存在其它可能；第二段则是非空小写字符串、`Z`（表示 `ZHONGJIANWANGLE`）、`E` 三者之一；最后一段是非空小写字符串、`H`（表示 `HOUMIANWANGLE`）、`E` 三者之一。 ## Output 一行一个整数，表示所有记录串中，能匹配的最多的复制的数目。 [samples] ## Background > 好像忘了什么事…… 算了，想必不是什么重要的事吧。 ## Note ### 样例 1 解释你希望这个串是 `nflsalgonflspcqidong`。你确信，不会再有其它串比它更匹配现存的记录了。 ### 数据范围与约定对于所有数据，保证输入的所有字符串长度之和不超过 $5\times 10 ^ 5$。 - 子任务 1（$30$ 分）：保证所有复制的 “后面” 段都是 `H`。 - 子任务 2（$70$ 分）：无特殊限制。 Source：NFLSPC #6 K by Troverld

Samples

Input #1

3
nflsalgo Z H
Q nflspc H
Q Z qidong

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[NFLSPC #6] 啊，忘记了。",
    "description": {
      "content": " 你在你的电脑上发现了 $n$ 份文本。冥冥之中，你没来由地感觉这似乎全都是一份记录的复制。 - 首先，原始记录是一个长度未知（甚至可以为空）的字符串，称作 **记录串**。对于一份复制，其将记录串切成了三段 **可以为空** 的字符串 **片段**。**每份复制中切割方案不保证相同**。你暂且将这三份 **片段** 依次称作 **前面**，**中间** 和 **后面**。 - 某些复制中的某",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9935"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你在你的电脑上发现了 $n$ 份文本。冥冥之中，你没来由地感觉这似乎全都是一份记录的复制。\n\n- 首先，原始记录是一个长度未知（甚至可以为空）的字符串，称作 **记录串**。对于一份复制，其将记录串切成了三段 **可以为空** 的字符串 **片段**。**每份复制中切割方案不保证相同**。你暂且将这三份 **片段** 依次称作 **前面**，**中间** 和 **后面**。\n- 某些复制中的某些片...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments