이모티콘 :-)

시간 제한1초메모리 제한128 MB

요약

여러 이모티콘 문자열이 주어질 때, 각 줄에서 이모티콘이 연속으로 나타나지 않도록 텍스트의 최소 문자 수를 공백으로 바꾸는 문제다.

난이도: 보통10점 중 7점
유형: 문자열 매칭, 동적 계획법, 트라이, 문자열
정답자: 아직 제출이 없습니다

문제

이모티콘은 채팅이나 이메일에서 단어로 표현하기 어려운 감정을 나타낼 때 자주 쓰인다. 여러모로 편리하지만, 이모티콘을 몹시 성가시게 여겨 없애고 싶어 하는 사람도 많다.

세종이가 바로 그런 사람이다. 세종이는 이모티콘이 너무 싫은 나머지 온 세상의 이메일에서 이모티콘을 지워 버리기로 마음먹었고, 이 계획을 돕는 특별한 프로그램을 당신과 함께 만들려고 한다.

프로그램은 먼저 지워야 할 이모티콘 목록을 입력받는다. 각 이모티콘은 공백을 포함하지 않는 문자열이다. 이어서 텍스트도 함께 입력받는다. 프로그램이 할 일은 텍스트의 일부 글자를 공백으로 바꿔, 원래 텍스트에 들어 있던 모든 이모티콘을 지우는 것이다. 어떤 이모티콘이 텍스트에 나타났다고 보는 것은, 그 이모티콘의 글자들이 한 줄 안에서 연속으로 이어져 등장할 때뿐이다. 즉 이모티콘의 글자들 사이에 공백이나 다른 글자가 끼어들면 그것은 이모티콘으로 치지 않는다.

세종이의 계획이 최대한 들키지 않도록, 공백으로 바꾸는 글자의 개수를 최소로 해야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 이모티콘의 개수 $N$ 과 텍스트의 줄 수 $M$ 이 주어진다. 이어지는 $N$ 개의 줄에는 길이가 $15$ 이하인 비어 있지 않은 이모티콘이 한 줄에 하나씩 주어진다. 그다음 $M$ 개의 줄에는 이모티콘을 지울 대상 텍스트가 주어지며, 각 줄의 길이는 $80$ 이하이다. $1 \le N, M \le 100$ 이라고 가정해도 좋다.

이모티콘은 영어 대소문자, 숫자, 그리고 특수문자 !?.,:;-_'#$%&/=*+(){}[](큰따옴표는 포함되지 않는다)로만 이루어질 수 있다. 텍스트에는 여기에 더해 공백 문자도 들어갈 수 있다.

입력의 끝에는 $N = M = 0$ 인 줄이 주어진다.

출력

각 테스트 케이스마다 한 줄에 하나씩, 그 테스트 케이스의 모든 텍스트에서 이모티콘을 모두 지우기 위해 공백으로 바꿔야 하는 글자의 최소 개수를 출력한다.

예제6

예제 1

입력

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

예상 출력

11
8

예제 2
입력
```
1 1
:)
hi :) there
0 0
```
예상 출력
```
1
```
예제 3
입력
```
1 1
xy
abc
0 0
```
예상 출력
```
0
```
예제 4
입력
```
1 1
aa
aaaa
0 0
```
예상 출력
```
2
```
예제 5
입력
```
2 1
ab
b
ab
0 0
```
예상 출력
```
1
```
예제 6
입력
```
1 1
:)
: )
0 0
```
예상 출력
```
0
```