31420번 - 문자열 - 그래프 매칭

다음과 같은 방식으로 알파벳 소문자로 이루어진 문자열을 이용해 그래프를 만들 수 있다.

1. 알파벳 소문자 a부터 z까지에 대응되는 정점을 만든다.
2. 길이가 $L$인 문자열 $S$를 $S_1S_2S_3\cdots S_L$로 나타냈을 때, $L-1$ 이하인 모든 양의 정수 $i$에 대해 $S_i \to S_{i+1}$인 간선을 그래프에 추가한다. 이때 같은 간선이 여러 개일 경우 한 개만 추가한다.

알파벳 소문자에 대응되는 정점들로 이루어진 그래프와 문자열 $T$가 주어졌을 때, 위 변환 과정을 통해 주어진 그래프와 동일한 그래프가 만들어지는 $T$의 부분 문자열의 개수를 구하시오.

여기서 부분 문자열이란, 문자열의 앞뒤에서 원하는 길이만큼 잘라서 얻을 수 있는 길이 $1$ 이상의 문자열을 의미한다. 예를 들어 abcde라는 문자열이 있을 때, cd나 abc는 부분 문자열이지만, bd는 문자열의 앞 뒤에서 어떤 길이로 잘라내도 얻어낼 수 없으므로 부분 문자열이 아니다.

첫 번째 줄에 문자열의 길이를 나타내는 정수 $N$이 주어진다. $(2 \le N \le 2\, 000\,000)$

두 번째 줄에 문자열 $T$가 주어진다. $T$는 알파벳 소문자로만 이루어진 길이 $N$짜리 문자열이다.

세 번째 줄에 그래프의 간선 개수를 나타내는 정수 $M$이 주어진다. $(1 \le M \le 26^2)$

네 번째 줄부터 $(M + 3)$번째 줄까지 그래프의 간선을 나타내는 알파벳 소문자 $2$개가 공백 없이 주어진다.

$1 \le i \le M$인 $i$에 대해 $(i + 3)$번째 줄에 $x_iy_i$가 입력으로 주어졌다면 이는 $x_i \to y_i$인 간선을 의미한다. $x_i$와 $y_i$는 같은 문자일 수 있으며, 같은 간선이 여러 번 주어지지 않는다. 주어지는 간선은 방향이 있는 간선임에 유의한다.

첫 번째 줄에 지문에서 언급된 그래프 변환 과정을 거쳤을 때 동일한 그래프가 만들어지는 문자열 $T$의 부분 문자열의 개수를 출력한다.