String Matching
Tag(s):

## Algorithms, Dynamic Programming, Easy-Medium

Problem
Editorial
Analytics

Given a string X formed out of single digit numbers from $0 - 9$ , 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 \le |X| \le 10^5$
$1 \le n \le 10$

SAMPLE INPUT
333
1
3

SAMPLE OUTPUT
6
Explanation

There are 6 substrings that have 3 in them

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 1024 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

August Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Graphs
• Math > Combinatorics