문자열 복원하기
시간 제한2초메모리 제한128 MB
주어진 길이 k 부분 문자열 집합에 속하도록 제한된 길이 L 문자열의 개수를 세는 문제로, 겹침 관계를 이용한 자동 상태 전이 DP로 풉니다.
문제
문자열 S와 양의 정수 k에 대해, S에 등장하는 길이 k의 부분문자열들의 집합을 T(S, k)라고 하자. 같은 부분문자열이 여러 번 등장해도 집합에는 한 번만 포함된다. 예를 들어 S = "ABABA", k = 2이면 T(S, k) = {"AB", "BA"}이다.
N종류의 문자로 이루어진 길이 k 문자열들의 집합 X가 주어진다. 길이가 L인 문자열 S 중에서 T(S, k)가 X의 부분집합이 되는 것의 개수를 구하라.
예를 들어 L = 5이고 X = {"ABB", "BCA", "BCD", "CAB", "CDD", "DDA"}인 경우, 조건을 만족하는 문자열은 "BCABB"와 "BCDDA" 두 개이다.
입력
첫째 줄에 N(1 <= N <= 26), L(1 <= L <= 100), M(1 <= M <= 600)이 주어진다. M은 집합 X의 크기이다.
이어서 X에 속한 M개의 문자열이 공백으로 구분되어 주어진다. X의 모든 문자열은 길이가 같고, 그 길이는 10 이하이다. 입력에는 대문자만 사용된다.
출력
조건을 만족하는 길이 L 문자열 S의 개수를 출력한다. 정답은 2^31 - 1보다 작다.