EMOTICON - Emoticons

no tags 

Emoticons are used in chat and e-mail conversations to try to express the emotions that printed words cannot. This may seem like a nice feature for many, but a lot of people find it really annoying and wants to get rid of emoticons.

George is one of those people. He hates emoticons so bad, that he is preparing a plan to remove all emoticons from all e-mails in the world. Since you share his visionary plans, you are preparing a special program to help him.

Your program will receive the list of emoticons to proscribe. Each emoticon will be a string of characters not including any whitespace. You will also receive several lines of text. What you need to do is change some characters of the text into spaces to ensure no emoticon is left on the text. For an emoticon to be considered to appear in the text it has to appear in a single line and be made of consecutive characters.

To help George’s plan remain secret as long as possible, you need to do your job with the minimum possible amount of character changes.

Input

The input file contains several test cases. Each test case consists of several lines. The first line of each test case will contain two integers separated by a single space: N, the number of emoticons to proscribe, and M, the number of lines the text has. The next N lines contain one emoticon each, a non-empty string of at most 15 characters. Each of the last M lines of the test case contains a line of text of at most 80 characters. You can assume 1 <= N,M <= 100.

Valid input characters for emoticons are uppercase and lowercase letters, digits and the symbols “!?.,:;-_’#$%&/=*+(){}[]” (quotes for clarity). Each line of the text may contain the same characters with the addition of the space character.

The input is terminated by N = M = 0.

Output

For each test case, output exactly one line containing a single integer that indicates the minimum number of changes you need to make to the entire text to ensure no emoticon on the list appears in it.

Example

Input:
4 6
:-)
:-(
(-:
)-:
Hello uncle John! :-) :-D
I am sad or happy? (-:-(?
I feel so happy, my head spins
(-:-)(-:-)(-:-)(-:-) :-) (-: :-)
but then sadness comes :-(
Loves you, Joanna :-)))))
3 1
:)
):
))
:):)):)):)):(:((:(((:):)
0 0

Output:
11
8

hide comments
Sigma Kappa: 2017-06-22 20:50:37

Amazing problem. Combined two techniques to get Accepted.

hodobox: 2016-12-04 23:46:23

lots of test cases.

jorker_71: 2016-09-26 17:22:20

the 2007 ACM south American Programing contest

The Mastermind: 2016-03-21 05:24:41

@Rishav Goyal: nice, I got the same fault

Rishav Goyal: 2014-05-10 09:11:12

is it possible that one emoticon is substring of another amoticon. ~!! ??

Yes.! I got AC after assuming this.!! What a DP!!...
Took so much time to debug !! but fnially ^^__^^

Last edit: 2014-05-10 12:11:08
:F: 2013-12-07 23:17:54

getting wrong ans .... any complex case ??? plz ....


Added by:Camilo Andrés Varela León
Date:2007-12-02
Time limit:0.560s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:The 2007 ACM South American Programming Contest