키워드 검색

인터넷 정보의 양은 폭발적으로 늘어나고 있다. 이런 정보의 시대에는 찾으려는 정보가 있는 웹 페이지에만 들어가야 시간을 절약할 수 있으며, 이를 위한 가장 중요한 방법이 바로 키워드 검색이다. 많은 검색 엔진이 키워드 검색을 지원하고, 이를 통해 유용한 정보를 담은 페이지에 접근할 수 있다.

키워드 검색에는 여러 가지 변형이 있다. 주어진 텍스트에서 문자열 하나만 찾으면 되는 경우에는 문제가 꽤 쉬워진다. 이럴 때는 여러 문자열에서 패턴을 찾거나 정규표현식을 이용해서 찾으면 된다.

이 문제에서는 여러 개의 기본 문자열이 주어진다. 기본 문자열들을 어떤 순서로든 모두 이어 붙여 하나의 문자열을 만든 뒤, 그 이어 붙인 문자열을 주어진 텍스트에서 찾아야 한다. 이어 붙일 때 모든 기본 문자열을 정확히 한 번씩 사용하므로, 이어 붙인 문자열의 길이는 모든 기본 문자열 길이의 합과 같다.

예를 들어 기본 문자열이 aa, b, ccc이면 세 문자열을 모두 이어 붙여 만들 수 있는 문자열은 다음 여섯 가지이며, 각각을 텍스트에서 찾아야 한다: aabccc, aacccb, baaccc, bcccaa, cccaab, cccbaa.

이렇게 이어 붙인 문자열이 텍스트에서 등장하는 위치의 개수를 세어야 한다. 즉, 기본 문자열들을 모두 이어 붙여 만들 수 있는 문자열 중 하나와 같은 부분 문자열이 시작되는 위치의 개수를 센다.

두 개 이상의 문자열을 이어 붙인 결과가 서로 같을 수도 있는데, 이 경우를 어떻게 처리해야 하는지는 문제 설명을 조금 자세히 읽으면 알 수 있다. 예를 들어 기본 문자열이 x와 xx이면 두 순서 모두 xxx가 되며, 위치의 개수를 세므로 xxx는 한 문자열로 취급한다.

등장 구간은 겹칠 수 있다. 예를 들어 xxxx에는 서로 다른 두 위치에서 xxx가 시작되므로, 개수에 2를 더한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 $n$과 $m$, 즉 기본 문자열의 개수와 텍스트의 줄 수가 주어지며 $1 \le n \le 12$이다.

다음 $n$개의 줄에는 각각 기본 문자열이 하나씩 주어진다. 각 기본 문자열의 길이는 1 이상 20 이하이다.

다음 $m$개의 줄은 텍스트이다. 텍스트가 길어질 수 있어 $m$개의 줄로 나뉘어 있지만, 줄바꿈은 텍스트의 일부가 아니므로 검색할 때 무시해야 한다. 각 줄의 길이는 최대 100이고, 텍스트 전체의 길이는 최대 5000이다. 텍스트는 비어 있지 않다.

기본 문자열과 텍스트는 알파벳 소문자로만 이루어져 있다.

입력의 마지막 줄에는 0이 두 개 주어진다.

주의: $12! \times 5000$은 $2^{31}$보다 훨씬 크다.

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