단어 세기

시간 제한1초메모리 제한128 MB

요약

각 간선에 문자열이 붙은 루트 트리에서 루트에서 리프로 가는 모든 경로를 따라 주어진 단어가 나타나는 위치 쌍의 개수를 센다.

난이도: 어려움10점 중 8점
유형: 문자열 매칭, 트라이, DFS, 트리
정답자: 아직 제출이 없습니다

문제

탈레스는 먼 섬에서 다음과 같은 게임을 만들었다. 단어 하나를 고른 뒤, 길을 따라 적힌 글자들 속에서 그 단어가 몇 번 나타나는지 세는 것이다. 그는 게임을 더 어렵게 만들기 위해, 현재 위치에서 집으로 돌아가는 배를 탈 수 있는 항구들까지 이어지는 모든 경로를 지도에 그렸다.

길은 트리를 이룬다. 서로 다른 경로는 시작 부분을 공유할 수 있지만, 한 번 갈라진 두 경로는 다시 만나지 않으며, 모든 경로는 서로 다른 항구에서 끝난다. 노드 $0$ 은 시작점(단어를 고르는 곳)이고, 나머지 노드는 길이 갈라지는 지점이거나 항구(잎)이다. 각 도로 구간(간선)에는 소문자 알파벳으로 이루어진 문자열이 적혀 있다.

시작점에서 항구들로 가는 모든 경로를 따라, 고른 단어가 나타나는 서로 다른 출현의 개수를 세는 것이 당신의 과제이다.

입력

첫째 줄에 노드의 개수를 나타내는 정수 $N$ ( $2 \le N \le 15000$ )이 주어진다.

다음 $N - 1$ 개의 줄에는 각각 하나의 도로 정보가 주어진다. 두 정수 $I$ 와 $J$ ( $0 \le I, J \le N - 1$ ), 그리고 길이가 $L$ ( $1 \le L \le 1000$ )인 문자열 $S$ 가 주어지며, 이는 노드 $I$ 에서 노드 $J$ 로 향하는 도로에 문자열 $S$ 가 적혀 있음을 뜻한다. 이때 $I$ 는 항상 $J$ 의 부모이다. 노드 $0$ 으로 들어오는 도로는 없고, 항구에서 시작하는 도로도 없다.

마지막 줄에는 세어야 할 단어가 주어진다. 등장하는 모든 글자는 소문자 알파벳이다.

출력

시작점에서 항구들로 가는 모든 경로를 따라 단어가 나타나는 서로 다른 출현의 개수를 정수 하나로 출력한다.

힌트

하나의 출현은 시작 위치와 끝 위치로 식별되며, 끝 위치는 경로를 따라 시작 위치 뒤에 온다. 시작 위치부터 끝 위치까지(양 끝 포함) 연속으로 읽은 글자들이 정확히 그 단어를 이룰 때에만 출현이 존재한다. 두 출현은 시작 위치나 끝 위치가 다르면 서로 다른 것으로 본다.

경로들은 앞부분을 공유하다가 갈라지므로, 공유되는 부분에만 놓인 출현은 한 번만 세고, 갈라지기 전에는 겹치지만 서로 다른 가지에서 끝나는 출현들은 각각 따로 센다.

예제 입력에서 단어 honey는 경로의 다음 부분들을 따라 네 번 나타난다: (0-7-6), (0-7-8), (0-7-2-5), (2-4).

예제 트리

예제3

예제 1

입력

11
0 7 who
7 8 neyz
7 1 me
7 2 ne
2 3 ver
2 4 sthoneyz
2 5 y
7 6 ney
6 9 yenoh
6 10 xyz
honey

예상 출력

예제 2
입력
```
4
0 1 ab
1 2 c
1 3 c
abc
```
예상 출력
```
2
```
예제 3
입력
```
4
0 1 abc
1 2 x
1 3 y
abc
```
예상 출력
```
1
```