Aho-Corasick

문제

텍스트 $T$와 $N$개의 패턴이 주어진다. 텍스트에서 각 패턴이 등장하는 횟수의 총합을 구하라. 서로 다른 패턴이 텍스트의 같은 위치에서 겹쳐서 나타나더라도 각각 따로 센다. 또한, 하나의 패턴이 텍스트 내의 여러 위치에서 겹쳐서 나타나는 경우도 모두 포함하여 센다.

아호-코라식(Aho-Corasick) 알고리즘을 사용하여 풀어라.

입력

첫째 줄에 텍스트 $T$가 주어진다.
둘째 줄에 패턴의 개수 $N$이 주어진다.
셋째 줄부터 $N$개의 줄에 걸쳐 각 패턴이 한 줄에 하나씩 주어진다.

제한

• $1 \le |T| \le 10^6$
• $1 \le N \le 1,000$
• 모든 패턴의 길이 합 $\le 10^6$
• $T$와 모든 패턴은 영어 소문자로만 이루어져 있다.

출력

텍스트 $T$에서 $N$개의 패턴이 나타나는 총 횟수를 정수로 출력하라.

예제 입력 1

abcabc
3
abc
bc
c

예제 출력 1

6

예제 입력 2

aaaa
2
a
aa

예제 출력 2

7