开始: 2023-10-11 09:00:00

1012赛前模拟赛08

结束: 2023-10-18 15:00:00
当前  2025-01-24 17:43:49  类型: IOI  状态: 已经结束 

P1. 统计子序列
描述

作为字符串属性的魔法师,小R有一件史诗级法宝——字符串S 作为小R的粉丝,小P努力修炼,深入险境,只为获得和小R类似的法宝,经过数十年的积累,小P获 得了n个字符串,现在小P想知道,这n个字符串有多少个在S中出现。

请你帮他统计一下一个字符串t在S中出现,是指t为S的一个子序列

输入

第一行一个字符串S 

第二行一个正整数n 

接下来n行,每行一个字符串c[i] 

输出

一行一个整数表示答案 

样例

输入

abcde
4
a
bb
acd
ace

输出

3

输入

babaaaa
5
abaaab
aaaaaaa
aa
aaaaaaa
ab

输出

2

输入

a
1
a

输出

1
提示

对于20%的数据: |S|<=50000,n<=200 

对于50%的数据: |S|<=50000,n<=2000 

对于100%的数据: |S|<=50000,n<=5000,|c[i]|<=50

提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交