对于一个字符串我们定义
子串:串中任意个连续的字符组成的非空子序列,例如"abcda"的子串有 "a", "bc", "abc", "bcda", "abcdas"
前缀:从第一个字符开始的子串,例如字符串"abcda"的前缀有 "a", "ab", "abc", "abcd", "abcda"
现给出一个字符串 s 与 n 个字符串 t_i,现请你求出所有 t_i 中有多少子串是 s 的前缀
(注意,本题三个版本唯一的区别只有输入的数据范围不同)
第1行一个字符串 s
第2行一个整数 n
第3至n+2行若干个字符串 t_i
一个整数,表示 t_i 的子串中有多少是 s 的前缀
输入样例
abcda 1 abcab
输出样例
5
s 与 t 只包含小写英文字符
s 的长度不超过 500
所有 t_i 的长度总和不超过 500
n 不超过 500