아스키 거리
시간 제한4초메모리 제한512 MB
거리 문자열과 여러 타일 패턴이 주어질 때, 어떤 패턴으로도 덮이지 않는 위치의 개수를 구하는 문제로 아ho-corasick 같은 다중 문자열 매칭 기법이 필요합니다.
문제
상근이네 집 앞의 아스키 거리는 소문자 알파벳이 적힌 타일 N칸으로 이루어져 있다. 정부는 알 수 없는 이유로 거리의 타일을 자주 교체하지만, 글자가 적힌 타일의 공급이 부족해 M종류의 묶음 타일만 사용할 수 있다.
i번째 묶음 타일에는 Li개의 글자가 적혀 있다. 묶음 타일은 회전할 수 없고, 일부만 잘라 사용할 수도 없다. 거리에서 연속한 칸들의 글자가 묶음 타일의 글자와 정확히 일치할 때에만 그 묶음으로 해당 칸들을 교체할 수 있다. 교체 구간끼리는 서로 겹쳐도 되고, 같은 묶음 타일을 여러 번 사용해도 된다.
현재 거리에 적힌 문자열과 사용할 수 있는 묶음 타일들이 주어진다. 어떤 묶음 타일로도 교체할 수 없는 칸의 수를 구하라.
입력
첫째 줄에 거리의 길이 N이 주어진다. 둘째 줄에 현재 거리의 각 칸에 적힌 소문자 알파벳 문자열이 주어진다. 셋째 줄에 묶음 타일의 종류 수 M이 주어진다. 다음 M개 줄에는 각 묶음 타일에 적힌 소문자 알파벳 문자열이 하나씩 주어진다.
제한은 다음과 같다.
- 1 ≤ N ≤ 300,000
- 1 ≤ M ≤ 5,000
- 1 ≤ 각 묶음 타일의 길이 ≤ 5,000
출력
첫째 줄에 어떤 묶음 타일로도 교체할 수 없는 거리 칸의 수를 출력한다.