프로그램 명: coci_poplo
제한시간: 4 초
미코의 ASCII 길거리는 N개의 영어 소문자로 만들어졌다. 주 정부가 정기적으로 길을 정비하지만
글자타일은 가격이 상당히 비싸서 정부는 오직 M개의 다른 패턴의 소문자 타일을 가지고 있다.
i번째의 타일의 패턴은 Li개의 소문자 알파벳으로 이루어져있다.
타일은 회전하거나 조각낼수 없으며, 오직 길에 알맞은(적절한 패턴으로 된)
연속된 알파벳으로 이루어져 있다.
타일은 쌓을 수 있으며 여러개의 타일을 같은 패턴으로 사용할 수 있다.
만약 길에 대체할 패턴의 타일이 없으면 그곳에는 타일을 둘 수 없다.
타일을 둘 수 없는 공간의 숫자를 계산하시오.
입력
- 첫번째 줄에 정수 N, 길의 길이를 입력한다. (1 < N< 300,000)
- 두번째 줄에 N개의 연속하는 알파벳 소문자를 입력한다.
- 세번째 줄에 M개의 타일의 패턴 갯수를 입력한다. (1 < M < 5,000)
- 각각의 M개의 줄에 Li개의 타일 패턴을 입력한다.(1 < Li < 5,000)
(각각의 타일 패턴은 영어 소문자로 입력한다.)
출력
타일을 둘 수 없는 공간의 최소 개수를 출력하시오.
Mirko's ASCII street is made of N lowercase letters of the English alphabet. The city government
occasionally replaces the tiles in the street. However, the letter tiles are in high demand, so the
government has only M different tile patterns available.
The i th tile pattern consists of Li letters. A tile cannot be rotated or broken into pieces, and it can only
be placed such that the tile letters coincide with the contiguous letter subsequence in the street.
Tiles can overlap and we can use multiple tiles of the same pattern.
A street cell is untileable if it cannot be covered by any tile. Compute the number of untileable cells.
입력
The first line of input contains the positive integer N (1 ≤ N ≤ 300 000), the length of the street.
The second line of input contains N lowercase English letters, the letter sequence in the street.
The third line of input contains the positive integer M (1 ≤ M ≤ 5000), the number of tile patterns.
Each of the next M lines contains a description of a tile pattern with length Li (1 ≤ Li ≤ 5000). The tile
pattern descriptions consist of lowercase English letters.
출력
The first and only line of output must contain the required number of untileable cells.
입출력 예
입력
6
abcbab
2
cb
cbab
출력
2
입력
4
abab
2
bac
baba
출력
4
입력
6
abcabc
2
abca
cab
출력
1
출처:coci 2011-2012 contest5 6/6
번역: kdkim89
[질/답]
[제출 현황]
[푼 후(0)]