String Matching

4

21 votes
Algorithms, Dynamic Programming, Easy
Problem

Given a string X formed out of single digit numbers from 09 , you are given a set of digits S and you need to count total substring of string X that contains all the digits in the set S.
Input
First line contains a string as input. Next line contains a number n as input denoting size of set S. Next line contains n space separated integers that denote the distinct integers in the set S.
Output
In the output you have to give total count of substrings of the string X such that they contain all the digits in the set S
Constraints
1|X|105
1n10

Sample Input
333
1
3
Sample Output
6
Time Limit: 1
Memory Limit: 1024
Source Limit:
Explanation

There are 6 substrings that have 3 in them

Editor Image

?