{"problem":{"name":"[JRKSJ R6] Dedicatus545","description":{"content":"对于字符串 $x,y$，定义 $w(x,y)$ 为 $x$ 在 $y$ 中的出现次数。 Index 给了你 $n$ 个字符串 $s_{1\\dots n}$，$m$ 次询问，每次询问给定 $l,r,k$，求 $\\max_{i=l}^r w(s_i,s_k)$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8571"},"statements":[{"statement_type":"Markdown","content":"对于字符串 $x,y$，定义 $w(x,y)$ 为 $x$ 在 $y$ 中的出现次数。\n\nIndex 给了你 $n$ 个字符串 $s_{1\\dots n}$，$m$ 次询问，每次询问给定 $l,r,k$，求 $\\max_{i=l}^r w(s_i,s_k)$。\n\n## Input\n\n第一行两个整数 $n,m$。\\\n下面 $n$ 行，每行一个只包含小写字母的字符串表示 $s_{1\\dots n}$\\\n下面 $m$ 行，每行三个整数 $l,r,k$ 表示询问。\n\n## Output\n\n对于每个询问，每行输出一个整数表示答案。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/im5jyatm.png)\n\n## Note\n\n### 数据规模\n本题采用捆绑测试。\n\n| $\\text{Subtask}$ | $n,q\\le$ | $\\sum\\vert s\\vert\\le$ | $\\text{Score}$ | 特殊性质 |\n| :----------: | :----------: | :----------: | :----------: |:----------: |\n| $1$ | $2\\times10^3$ | $10^4$ | $20$ | 无 |\n| $2$ | $5\\times10^4$ | $3\\times 10^5$ | $20$ | 无\n| $3$ | $10^5$ | $5\\times10^5$ | $20$ | 所有字符串互不相同 |\n| $4$ | $10^5$ | $5\\times10^5$ | $40$ | 无\n\n对于 $100\\%$ 的数据，$1\\le n,m\\le 10^5$，$1\\le \\sum |s|\\le 5\\times 10^5$，$1\\le l\\le r\\le n$，$1\\le k\\le n$。\n\nData：abruce&critnos&fjy666","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8571","tags":["2022","洛谷原创","后缀自动机 SAM","O2优化","分治","虚树","分块","AC 自动机"],"sample_group":[["6 3\ndedicatus\na\nmisaka\nmikoto\nmi\naaa\n1 5 6\n1 2 4\n1 5 4","3\n0\n1"]],"created_at":"2026-03-03 11:09:25"}}