키워드 검색

인터넷에 있는 정보의 양은 급속하게 증가하고 있다. 이런 정보의 폭발 시대에서는 찾으려고 하는 정보가 있는 웹 페이지만 들어가야 시간을 절약할 수 있다. 그러기 위해서 가장 중요한 검색 방법은 키워드 검색이다. 많은 검색 엔진은 키워드 검색을 사용할 수 있고, 키워드 검색을 통해서 유용한 정보를 포함하는 페이지에 접근할 수 있다.

키워드 검색에는 많은 변형이 있다. 만약 주어진 텍스트에서 문자열 하나를 찾는 경우에는 상당히 문제가 쉬워진다. 이러한 경우에는 여러 문자열에서 패턴을 찾거나 정규표현식을 이용해서 찾으면 된다.

이 문제는 문자열(기본 문자열)이 여러 개가 주어진다. 기본 문자열을 적절히 합쳐 한 문자열로 만든 뒤 이 문자열을 주어진 텍스트에서 찾아야 한다.

예를 들어, 기본 문자열이 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보다 매우 크다.

각 테스트 케이스에 대해서, 문자열이 등장하는 위치의 개수를 출력한다.