BOJ 29960 Lühisõnum 8
BOJ 29960 Lühisõnum 8
문제 내용
개의 문자열이 주어집니다. 주어진 모든 문자열을 부분 문자열로 가지는 가장 짧은 문자열을 아무거나 하나 찾아 출력하세요.
입력
첫 줄에는 이 주어지고, 다음 줄에 걸쳐서 알파벳 소문자로 이루어진 문자열이 한 줄에 하나씩 주어집니다.
8번 입력은 이고, 각각의 문자열의 길이는 10만 이하입니다.
출력
문제의 정답이 들어 있는 텍스트 파일을 제출합니다.
문제 풀이
스포일러
먼저, 한 문자열에 완전히 포함되는 다른 문자열이 있으면 그것들을 모두 제거합니다.
남은 문자열에 대해, 번째 문자열 뒤에 번 문자열이 올 때 겹칠 수 있는 최대 길이를 모든 의 쌍에 대해 구합니다. 이는 KMP, Z, 또는 해싱으로 구할 수 있습니다.
마지막으로, TSP DP를 하여 가능한 모든 순열 중에서 겹치는 길이의 총합이 가장 큰 것을 구하고, 그 결과를 역추적하여 답을 구성합니다.
Last updated on