시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 128 MB | 16 | 3 | 3 | 100.000% |
인터넷에 있는 정보의 양은 급속하게 증가하고 있다. 이런 정보의 폭발 시대에서는 찾으려고 하는 정보가 있는 웹 페이지만 들어가야 시간을 절약할 수 있다. 그러기 위해서 가장 중요한 검색 방법은 키워드 검색이다. 많은 검색 엔진은 키워드 검색을 사용할 수 있고, 키워드 검색을 통해서 유용한 정보를 포함하는 페이지에 접근할 수 있다.
키워드 검색에는 많은 변형이 있다. 만약 주어진 텍스트에서 문자열 하나를 찾는 경우에는 상당히 문제가 쉬워진다. 이러한 경우에는 여러 문자열에서 패턴을 찾거나 정규표현식을 이용해서 찾으면 된다.
이 문제는 문자열(기본 문자열)이 여러 개가 주어진다. 기본 문자열을 적절히 합쳐 한 문자열로 만든 뒤 이 문자열을 주어진 텍스트에서 찾아야 한다.
예를 들어, 기본 문자열이 aa, b, ccc일 때, 이 문자열을 합쳐서 만들 수 있는 문자열은 다음과 같이 6개가 있고, 각각을 텍스트에서 찾아야 한다. aabccc, aacccb, baaccc, bcccaa, cccaab, cccbaa
텍스트에는 이러한 문자열이 등장하는 횟수를 세야 한다. 즉, 텍스트에서 등장하는 문자열 위치의 개수를 세면 된다.
두 개 또는 그 이상의 문자열을 합친 것이 같을 수도 있다. 문제 설명을 조금 자세히 읽으면 이 경우를 어떻게 처리해야 하는지 알 수 있다. 예를 들어, 두 기본 문자열이 x와 xx일 때, 두 문자열을 합치면 둘 다 xxx가 된다. 문자열이 등장하는 위치의 개수를 세야하므로 이 경우에는 문자열 1개로 세면 된다.
문자열이 등장하는 구간이 겹칠 수도 있다. 예를 들어, xxxx에는 xxx가 두 번 등장한다. 이 경우에는 서로 다른 위치에서 등장하기 때문에, 두 가지로 계산한다.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 기본 문자열의 개수 n과 텍스트의 줄의 수 m이 주어진다. n은 1보다 크거나 같고, 12보다 작거나 같다.
다음 n개 줄은 기본 문자열이다. 이 문자열의 길이는 1보다 크거나 같고, 20보다 작거나 같다.
다음 m개 줄은 텍스트이다. 텍스트는 너무 길어질 수 있기 때문에, m줄로 나누어져 있다. 하지만, 줄바꿈은 텍스트의 일부가 아니며, 무시하고 검색을 해야 한다. 각 줄의 길이는 최대 100이며, 텍스트의 길이는 최대 5000이다. 텍스트는 비어있지 않다.
기본 문자열과 텍스트는 알파벳 소문자로만 이루어져 있다.
입력의 마지막 줄에는 0이 두 개 주어진다.
주의! 12!×5000은 231보다 매우 크다.
각 테스트 케이스에 대해서, 문자열이 등장하는 위치의 개수를 출력한다.
3 1 aa b ccc aabccczbaacccbaazaabbcccaa 3 1 a b c cbbcbcbabaacabccaccbaacbccbcaaaccccbcbcbbcacbaacccaccbbcaacbbabbabaccc 3 4 aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 0 0
5 12 197
ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2008 in Aizu G번