Christmas string
Tag(s):

## Easy-Medium

Problem
Editorial
Analytics

Little Santa has made a list of all the nice children to whom he have to give the present. While getting ready to deliver the gifts he forgot where he kept the list. He remembered a string S containing lowercase letters and stars ( * ). Star denotes that he didn't remember that letter of the string S.

Little Santa is wondering what is the maximum number of names of the nice children in the list that can possibly match with the string S if he will change at most one letter in the string S to a star. String A can possibly match with the string S if letters on non star positions are equal. He is getting late to deliver the gifts so he asked you to solve this.

Note: All the names and the string S will have same length.

Input format:
First line contains a string S $(1 \le |S| \le 3000)$, denoting the star string. S only contains lowercase letters and stars ( * ). Second line contains an integer N $(1 \le N \le 3000)$, denoting the number of names on the list. Next N lines contains a string each, $str_i$ $(1 \le |str_i| \le 3000)$, denoting the names of the children on the list. $str_i$ consists of only lowercase letters.

Output format:
Print an integer denoting the maximum number of names of the nice children in the list that can possibly match with the string S if he will change at most one letter in the string S to a star.

SAMPLE INPUT
a*c
3
abc
agd

SAMPLE OUTPUT
3

Explanation

We can substitute third character with * , as a result we'll get a**. All 3 strings match this one.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: 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, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Christmas Circuits '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Algorithms > String Algorithms