• O(n^2)개의 모든 이름 쌍에 대해서 연결 가능한지 여부를 확인하면 된다.
• 두개의 이름 n1, n2가 연결 가능한지를 확인하는 가장 나이브한 방법은, n1[:i] 와 n2[-i:]이 같은지를 1≤i≤min(|n1|,|n2|)+1 인 모든 i에 대해서 확인해보는 것이다. l= min(|n1|,|n2|) 이라 하면, O(l^2)의 시간이 걸린다.
• 조금 더 효율적인 방법은. n1과 n2를 이어붙인 문자열 S를 만들고, S의 border 중에서 길이가 l 이하인 것이 있는지 확인해보는 것이다. KMP알고리즘이나 Z알고리즘을 사용하면 O(|S|)에 처리할수 있다.
• 문자열의 최대 길이를 m이라고 하면, 연결 가능성을 확인하는 나이브한 방식은 O(m^2), 효율적인 방식은 O(m)이고, 전체 시간복잡도는 O(n^2*m^2) 또는 O(n^2*m)이 된다. 여기에서는 m의 범위가 최대20 으로 매우 작기 때문에, 나이브한 방식이 실제로는 더 빠르게 돌아간다.

"""Solution code for "BOJ 28064. 이민희진".

- Problem link: https://www.acmicpc.net/problem/28064
- Solution link: http://www.teferi.net/ps/problems/boj/28064
"""

import itertools


def main():
    N = int(input())
    names = [input() for _ in range(N)]

    answer = 0
    for n1, n2 in itertools.combinations(names, 2):
        if (any(n2.endswith(n1[:i]) for i in range(1, len(n1) + 1))) or (
            any(n1.endswith(n2[:i]) for i in range(1, len(n2) + 1))
        ):
            answer += 1

    print(answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 28064. 이민희진".

- Problem link: https://www.acmicpc.net/problem/28064
- Solution link: http://www.teferi.net/ps/problems/boj/28064
"""

import itertools
from teflib import string as tstring


def main():
    N = int(input())
    names = [input() for _ in range(N)]

    answer = 0
    for n1, n2 in itertools.combinations(names, 2):
        l = min(len(n1), len(n2))
        for s in [n1 + n2, n2 + n1]:
            z = tstring.z_array(s)
            if any(i == z_i <= l for i, z_i in enumerate(reversed(z), start=1)):
                answer += 1
                break

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.string.z_array