적절한 문자열 문제

시간 제한9초메모리 제한1024 MB

요약

서로 부분 문자열이 아닌 n개의 ACGT 문자열이 주어집니다. 모든 순서쌍 (i, j)에 대해 s_i의 진접미사이면서 s_j의 진접두사인 가장 긴 문자열의 길이를 구해 모두 더합니다.

문제

문자열 s의 접두사(prefix)이면서 s 자신이 아닌 문자열을 s의 적절한 접두사라 한다. 같은 방식으로 s의 접미사(suffix)이면서 s 자신이 아닌 문자열을 s의 적절한 접미사라 한다.

두 문자열 s, t에 대해 f(s, t)는 s의 적절한 접미사이면서 t의 적절한 접두사인 문자열 중 가장 긴 것의 길이로 정의한다.

A, C, G, T로만 이루어진 문자열 n개 s1, s2, ..., sn이 주어진다. 이 문자열들은 하나가 다른 하나의 부분문자열이 되지 않는다.

이때 $\sum_{i=1}^{n} \sum_{j=1}^{n} f(s_i, s_j)$ 를 구한다.

첫째 줄에 문자열의 개수 n이 주어진다. (1 이상 100,000 이하)

그다음 n개의 줄에 A, C, G, T로만 이루어진 문자열 s1, s2, ..., sn이 한 줄에 하나씩 주어진다. 한 문자열이 다른 문자열의 부분문자열이 되지 않는다. n개 문자열 길이의 합은 $10^7$ 이하이다.

빈 문자열도 적절한 접두사나 적절한 접미사가 될 수 있다.

입력 예제에서 f(s1, s1) = 4, f(s2, s1) = 6, f(s3, s1) = 6, f(s4, s1) = 3, f(s4, s2) = 4이고, 나머지 11개 값은 모두 0이다. 따라서 답은 4 + 6 + 6 + 3 + 4 = 23이다.