더 강력한 문자열

참고: 이는 문제 Mighty Strings의 (논란의 여지는 있지만) 더 어려운 버전이다. 각 버전에는 $50$점이 배정되어 있음에 유의하라. 두 버전은 문자열이 강력하다는 정의가 약간 다르며, 이 문제에서는 $T$이 더 클 수 있다.

$N$개의 문자열(중복을 포함할 수 있음)이 주어지며, 이를 $U$로 나타낸다.

$U$에서 $s$과 같은 문자열의 개수를 $f(s)$라고 하자. 부분 문자열(부분 문자열은 문자열의 시작 및/또는 끝에서 영 개 이상의 문자를 삭제하여 얻는 연속된 문자들의 수열이다. 문자열에 적어도 하나의 문자가 있으면 비어 있지 않다.) $s$이 $S$에 등장하는 횟수를 $g(S, s)$라고 하자. 예를 들어 $g(\texttt{aaaa}, \texttt{aa})=3$이다.

문자열 $S$은 다음 조건을 만족하면 강력하다.

$U$에 있는 문자열 중 강력한 문자열의 개수를 구하여라.

채점

제출한 풀이는 여러 테스트 그룹으로 이루어진 테스트에서 평가된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$1$| $T \leq 1000$

$2$ |$1$| $T \leq 10{,}000$

$3$ |$7$| $T \leq 10^5$

$4$ |$12$| $T \leq 10^6$

$5$ |$29$| 추가 제한 없음.

입력의 첫째 줄에는 문자열의 개수를 나타내는 정수 $N$ ($1 \leq N \leq 10^6$)이 주어진다.

이어지는 $N$개의 줄에는 각각 문자 a-z로 이루어진 비어 있지 않은 문자열이 주어진다. 이 문자열들이 $U$를 이룬다.

$U$에 있는 모든 문자열의 길이의 합을 $T$이라고 하자. $T \leq 5 \cdot 10^6$임이 보장된다. 입력의 양이 매우 많으므로 입력을 읽는 과정의 성능에 유의하라.

강력한 문자열의 개수를 나타내는 정수를 출력한다.

예제 $1$에서 a은 강력하다. 유일한 부분 문자열이 a이고, 이는 $U$에 있기 때문이다. 그러나 aa은 강력하지 않다. 부분 문자열은 a, a, aa이다. a은 $U$에 한 번만 등장하지만, aa에는 a이 부분 문자열로 두 번 등장한다. 비슷한 이유로 aaa도 강력하지 않다.

예제 $2$에서는 abc을 제외한 모든 문자열이 강력하다. abc은 부분 문자열 bc이 $U$에 존재하지 않으므로 강력하지 않다.