| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 9 초 | 1024 MB | 284 | 53 | 19 | 11.656% |
문자열 s의 접두사(prefix)이면서 s가 아닌 문자열을 s의 적절한 접두사라 한다. 같은 방식으로 s의 접미사(suffix)이면서 s가 아닌 문자열을 s의 적절한 접미사라 한다.
두 문자열 s, t에 대해 f(s, t)를 s의 적절한 접미사이면서 t의 적절한 접두사인 문자열 중 가장 긴 것의 길이로 정의한다.
A, C, G, T로만 이루어진 n개의 문자열 s1, s2, ..., sn이 주어진다. 이 문자열들은 하나가 다른 하나의 부분문자열(substring)이 아님이 보장된다.
이 때 $\sum_{i=1}^{n} {\sum_{j=1}^{n} {f(s_i, s_j)} }$를 구해 출력한다.
첫째 줄에 문자열의 개수 n이 주어진다. (1 ≤ n ≤ 100,000)
그 후 n개의 줄에 A, C, G, T로만 이루어진 문자열 s1, s2, ..., sn이 주어진다.
이 때 한 문자열이 다른 문자열의 부분문자열(substring)이 아니며, n개 문자열 길이 합은 107 이하이다.
4 TATTATT CTATTAT GTATTAT CCTAT
23
빈 문자열도 적절한 접두사 혹은 적절한 접미사가 될 수 있다.
입력 예제에서 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이다.