STRNGSLV - I Love Strings

Sacchi and Maurya are String lovers. They love to solve problems on strings. So our born-talented Priyun decided to ask them a problem on strings. He gave them a string of size S which consists of only small English letters. According to Priyun some of the alphabets are “Nice” and rest all are “Eww”. Now Priyun has a tolerance level of X “Eww”.
Priyun wants to know the distinct substrings of the given string which he can tolerate.
Even Sacchi and Maurya is finding it difficult to solve. So help them.

Input

The input file consists of several cases T (1<=T<=10).
The first line of each test case consists of a string S, [Size of S is <=2000].
S consists of only lowercase English Letters.
Next line contains the number P[0<=P<=26], the number of “Nice” Alphabets.
Next P lines contains an Alphabet that is Nice. All the P characters are distinct and it is between [a,z].
Next line contains an Integer X i.e. the tolerance level of Priyun.

Output

Print a single integer for each testcase i.e  the number of distinct substrings that Priyun can tolerate.

Example

Input:
1
bbbbbbbbba
1
b
0 Output: 9

Added by:Rajesh Kumar
Date:2014-11-25
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2017-06-09 17:56:05 Vipul Srivastava
Why O(n*n) doesn't work here?

Last edit: 2017-06-09 18:38:08
2017-04-20 00:28:42
The problems asks for 'how many distinct strings (strings which differ at least at one position) containing at most X characters not in the set {P nice characters from input} are substrings of S'
2015-12-11 09:51:03
why this website has so few comments?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.