http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1470. Polycarpus is Looking for Good Substrings
时间限制:4.0s   内存限制:256.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  现在有一个的字符串,都是有小写字母构成。再给你很多个集合。对于每个集合,求以下子串s[a,b]的数量:
  1.子串中出现的字母必须出现在集合中。
  2.集合中的字母必须在子串中找得到
  3.不存在比这个子串更长的子串s[x,y],使得s[x,y]满足1,2,且(x<=a<=b<=y,y-x+1>b-a+1)
输入格式
  第一行字符串s
  第2行包含一个正整数m。表示给你m个集合。
  接下来有m行,每行会给你一个集合ci,保证集合中每个元素各不相同,且都是小写字母。
输出格式
  输出m行,每行一个整数,第i行表示对于第i个集合,字符串中满足题意的子串的数量
样例输入
abacaba
3
ac
ba
a
样例输出
1
2
4
数据规模和约定
  1 ≤ |s| ≤ 106
  1 ≤ m ≤ 104