吃糖果¶

参考时间限制：1.0 秒（参考环境：评测环境与性能；仅供预估）
实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
内存限制：512 MB

背景故事¶

你得到了一串糖果，但只愿意吃其中符合自己口味的连续片段。给定你喜欢的糖果串，最多能从这串糖果中吃到多少段？这里统计的是吃到的段数，而不是不同糖果串的种类数。

每颗糖只能吃一次。所有片段都从原来的糖果串中选取，不能重叠，也不能把吃剩的部分重新拼接成新的片段。

形式化问题描述¶

给定一个非空二进制串 \(T\) 和 \(n\) 个非空二进制串 \(P_1,\ldots,P_n\) . 你可以选择若干个两两不相交的区间 \([l_i,r_i]\) ，使得每个子串 \(T[l_i\ldots r_i]\) 都等于某个 \(P_j\) . 同一个 \(P_j\) 可以匹配多个所选片段，清单中也允许出现相同的字符串。

求最多可以选择多少个区间。若 \(n=0\) ，答案为 \(0\) .

输入格式¶

第一行一个整数 \(n\) .

第二行一个非空二进制串 \(T\) .

接下来 \(n\) 行，每行一个非空二进制串 \(P_i\) .

输出格式¶

输出一个整数，表示最多能选择的片段数。

样例 1¶

输入¶

5
010101010111
010
01
11
1000
1110

输出¶

解释¶

可以依次选择五段 01 和最后一段 11 ，一共六段。

数据范围与保证¶

\(0\le n\le 100\,000\) .
\(1\le |T|\le 5\,000\,000\) .
\(\sum_{i=1}^{n}|P_i|\le 5\,000\,000\) ，且每个 \(P_i\) 非空。

数据分组¶

分值比例	额外条件
30%	\(\lvert T\rvert\le 1\,000\) ，\(\sum_{i=1}^{n}\lvert P_i\rvert\le 10\,000\)
20%	\(\lvert T\rvert\le 100\,000\) ，\(n\le 500\) ，每个 \(\lvert P_i\rvert\le 30\)
20%	所有 \(P_i\) 等长；\(\lvert T\rvert\) 和 \(\sum_{i=1}^{n}\lvert P_i\rvert\) 均不超过 \(5\,000\,000\)
30%	无额外条件