{"problem":{"name":"Ex - Taboo","description":{"content":"You are given a string $S$. Takahashi may perform the following operation $0$ or more times: *   Choose an integer $i$ such that $1 \\leq i \\leq |S|$ and change the $i$\\-th character of $S$ to `*`. T","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc268_h"},"statements":[{"statement_type":"Markdown","content":"You are given a string $S$. Takahashi may perform the following operation $0$ or more times:\n\n*   Choose an integer $i$ such that $1 \\leq i \\leq |S|$ and change the $i$\\-th character of $S$ to `*`.\n\nTakahashi's objective is to make $S$ not contain any of $N$ strings $T_1,T_2,\\ldots,T_N$ **as a substring**.  \nFind the minimum number of operations required to achieve the objective.\n\n## Constraints\n\n*   $1 \\leq |S| \\leq 5 \\times 10^5$\n*   $1 \\leq N$\n*   $N$ is an integer.\n*   $1 \\leq |T_i|$\n*   $\\sum{|T_i|} \\leq 5 \\times 10^5$\n*   $T_i \\neq T_j$ if $i \\neq j$.\n*   $S$ and $T_i$ are strings consisting of lowercase English letters.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$S$\n$N$\n$T_1$\n$T_2$\n$\\vdots$\n$T_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc268_h","tags":[],"sample_group":[["abcdefghijklmn\n3\nabcd\nijk\nghi","2\n\nIf he performs the operation twice by choosing $1$ and $9$ for $i$, $S$ becomes `*bcdefgh*jklmn`; now it does not contain `abcd`, `ijk`, or `ghi` as a substring."],["atcoderbeginnercontest\n1\nabc","0\n\nNo operation is needed."],["aaaaaaaaa\n2\naa\nxyz","4"]],"created_at":"2026-03-03 11:01:14"}}