뒤섞인 단어

Scrmable 교수는 검토 중이던 연구 논문에서 철자 오류를 발견했지만, 단어를 읽거나 이해하는 데에는 아무런 어려움이 없었다. 이에 관해 조사하던 중, 교수는 아래와 같은 흥미로운 글을 발견했다:

한 영국 대학의 연구에 따르면, 단어 안의 글자들이 어떤 순서로 놓이는지는 중요하지 않으며, 유일하게 중요한 것은 첫 글자와 마지막 글자가 올바른 위치에 있는 것이다. 나머지는 완전히 엉망이어도 여전히 아무 문제 없이 읽을 수 있다. 이는 인간의 정신이 각 글자를 하나씩 읽는 것이 아니라 단어 전체를 하나로 읽기 때문이다.

아니, 정확히 말하자면 ...

한 영국 대학의 연구에 따르면, 단어 안의 글자들이 어떤 순서로 놓이는지는 중요하지 않으며, 유일하게 중요한 것은 첫 글자와 마지막 글자가 올바른 위치에 있는 것이다. 나머지는 완전히 엉망이어도 여전히 아무 문제 없이 읽을 수 있다. 이는 인간의 정신이 각 글자를 하나씩 읽는 것이 아니라 단어 전체를 하나로 읽기 때문이다.

Scrmable 교수는 이 개념을 더 탐구하고 싶어 하며, 비슷하게 뒤섞인 단어들이 포함된 여러 문장을 모아 유명 출판물에 보내기 시작한다. 안타깝게도 교수의 키보드에서 스페이스 키가 작동하지 않아, 하나의 긴 문자열만 만들어졌다. 교수는 사전에 있는 단어 중 원래 형태 또는 뒤섞인 형태로 긴 문자열의 부분 문자열에 적어도 한 번 등장하는 단어가 몇 개인지 구해 달라고 요청했다. (뒤섞인 형태는 동일한 글자 집합으로 이루어지며 첫 글자와 마지막 글자는 같은 위치에 있고, 나머지 글자들은 임의의 순서로 놓인 형태이다.)

사전의 한 단어가 문자열에 여러 번 등장할 수 있음에 유의한다(적어도 한 번 나타나는지만 알면 되므로 한 번만 세어야 한다). 예를 들어 사전에 this라는 단어가 있다면, 유효하여 세게 되는 단어는 this(원래 형태)와 tihs(뒤섞인 형태)인 반면, tsih, siht 및 그 밖의 변형은 t로 시작하고 s로 끝나지 않으므로 유효하지 않다. 또한 tis, tiss, thiss는 원래 글자 집합을 재배열한 것이 아니므로 뒤섞인 형태가 아니다.

교수는 대단히 바쁘기 때문에 자신이 가장 아끼고 신뢰하는 연구 조교인 당신에게 이 작업을 맡긴다. 사전이 주어질 때, 사전의 단어 중 뒤섞인 형태 또는 원래 형태로 교수의 문자열에 부분 문자열로 적어도 한 번 등장하는 단어의 수를 셀 수 있는가?

제한

1 ≤ T ≤ 20. 메모리 제한: 1 GB. 사전에서 같은 두 단어는 없다. 사전의 각 단어 길이는 2 이상 $10^{5}$ 이하이다. 사전에 있는 모든 단어의 길이 합은 $10^{5}$을 초과하지 않는다. $S_{1}$와 $S_{2}$는 영문 소문자이다. 0 ≤ A ≤ $10^{9}$. 0 ≤ B ≤ $10^{9}$. 0 ≤ C ≤ $10^{9}$. 1 ≤ D ≤ $10^{9}$.

소규모 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 20초. 1 ≤ L ≤ 1000. 2 ≤ N ≤ 1000.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 150초. 1 ≤ L ≤ 20000. 2 ≤ N ≤ $10^{6}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다. 첫 줄에는 정수 L이 주어진다. 둘째 줄에는 영문 소문자로 이루어진 L개의 단어 목록이 주어지며, 이 단어들이 사전을 구성한다. 셋째 줄에는 두 영문 소문자 $S_{1}$와 $S_{2}$, 그리고 다섯 정수 N, A, B, C, D가 주어진다. $S_{1}$와 $S_{2}$는 교수의 문자열 S의 처음 두 문자이고, N은 S의 길이이며, 나머지 네 정수는 다음과 같이 S의 문자들을 생성하는 데 사용해야 하는 매개변수이다:

먼저 문자의 십진수 값 ord(c)와 십진수 n에 해당하는 문자 값 c 및 char(n)을 정의한다. 예를 들어, ord('a') = 97이고 char(97) = 'a'이다. 다른 변환은 ASCII 표를 참고할 수 있다.

이제 $x_{1}$ = ord($S_{1}$), $x_{2}$ = ord($S_{2}$)로 정의한다. 그런 다음 아래 점화식을 사용해 i = 3부터 N까지 $x_{i}$를 생성한다:

• $x_{i}$ = ( A * $x_{i-1}$ + B * $x_{i-2}$ + C )를 D로 나눈 나머지.

모든 i = 3부터 N까지에 대해 $S_{i}$ = char(97 + ( $x_{i}$을 26로 나눈 나머지 ))로 정의한다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y는 위에서 정의한 원래 형태 또는 뒤섞인 형태로 주어진 문자열의 부분 문자열에 등장하는 사전 단어의 수이다.

예제 케이스 #1에서 생성 방법을 사용해 만든 문자열 S는 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt이다. 사전 단어가 뒤섞인 형태 또는 원래 형태로 등장하는 부분은 다음과 같이 강조되어 있다:

• axpaj는 뒤섞인 형태인 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt로 등장한다.

• apxaj는 뒤섞인 형태인 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt로 등장한다. apxaj가 사전의 다른 단어 axpaj의 뒤섞인 형태이기도 하지만, 둘 다 세어야 함에 유의한다.

• dnrbt는 원래 형태인 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt로 두 번 등장하지만, 한 번만 세어야 한다.

• pjxdn는 뒤섞인 형태인 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt로 등장한다. 이 등장은 사전의 다른 단어가 등장하는 부분과 겹치지만, 그래도 각각 독립적으로 세어야 한다.

• abd는 전혀 등장하지 않는다.

참고: 이 문제의 대규모 데이터 세트에는 인터프리터 방식이거나 느린 언어를 사용하는 것을 권장하지 않는다.