{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"abcdefghijklmn\n3\nabcd\nijk\nghi"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"atcoderbeginnercontest\n1\nabc"},{"iden":"sample output 2","content":"0\n\nNo operation is needed."},{"iden":"sample input 3","content":"aaaaaaaaa\n2\naa\nxyz"},{"iden":"sample output 3","content":"4"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}