[JRKSJ R6] Dedicatus545

Luogu

IDLGP8571

Time1000ms

Memory512MB

DifficultyP7

2022洛谷原创后缀自动机 SAMO2优化分治虚树分块AC 自动机

对于字符串 $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)$。 ## Input 第一行两个整数 $n,m$。\ 下面 $n$ 行，每行一个只包含小写字母的字符串表示 $s_{1\dots n}$\ 下面 $m$ 行，每行三个整数 $l,r,k$ 表示询问。 ## Output 对于每个询问，每行输出一个整数表示答案。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/im5jyatm.png) ## Note ### 数据规模本题采用捆绑测试。 | $\text{Subtask}$ | $n,q\le$ | $\sum\vert s\vert\le$ | $\text{Score}$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: |:----------: | | $1$ | $2\times10^3$ | $10^4$ | $20$ | 无 | | $2$ | $5\times10^4$ | $3\times 10^5$ | $20$ | 无 | $3$ | $10^5$ | $5\times10^5$ | $20$ | 所有字符串互不相同 | | $4$ | $10^5$ | $5\times10^5$ | $40$ | 无对于 $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$。 Data：abruce&critnos&fjy666

Samples

Input #1

6 3
dedicatus
a
misaka
mikoto
mi
aaa
1 5 6
1 2 4
1 5 4

Output #1

3
0
1

API Response (JSON)

{
  "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}$\\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments