전체 금칙어 길이의 합을 이라고 하자.
1. 두 금칙어가 겹치는 경우
어떤 금칙어 의 비어 있지 않은 진접미사와 다른 금칙어 의 진접두사가 같은 문자열 라고 하자. 와 는 같은 금칙어여도 된다. 라 놓으면 이고, 다음과 같이 나타낼 수 있다.
메시지 에서 앞의 를 지우면 , 뒤의 를 지우면 가 남는다. 두 문자열의 길이는 모두 보다 작으므로 더 삭제할 수 없다. 따라서 이면 는 반례이며, 그 길이는 이다. 반대로 이면 이 두 삭제는 같은 문자열을 만든다.
2. 최소 반례에는 겹치는 두 금칙어만 있으면 된다
처리 결과가 달라지는 메시지가 존재한다고 가정하고, 그중 길이가 가장 짧은 것을 라고 하자. 보다 짧은 모든 메시지의 처리 결과는 하나로 정해진다.
에서 가능한 첫 삭제들을 살펴보자. 첫 삭제 후의 문자열들은 모두 보다 짧으므로 각각의 처리 결과가 유일하다. 에는 서로 다른 처리 결과가 있으므로, 이후의 처리 결과가 서로 다른 두 첫 삭제를 고를 수 있다.
두 삭제 구간이 같다면 한 번 삭제한 문자열도 같으므로 모순이다. 두 구간이 겹치지 않는다면 한쪽을 삭제한 후 다른 쪽도 삭제하여 같은 문자열에 도달할 수 있다. 첫 삭제 후의 처리 결과는 각각 유일하므로 이 경우에도 최종 결과가 같아져 모순이다.
따라서 두 삭제 구간은 일부 겹친다. 그 합집합을 로 나타내면 두 금칙어는 와 이다. 이면 두 첫 삭제 직후의 전체 문자열이 같아지므로 역시 모순이다. 그러므로 이고, 앞 절에 의해 합집합 자체가 반례이다. 그 길이는 이하이다.
따라서 정답은 인 모든 겹침에 대한 의 최솟값이다. 그런 겹침이 없으면 반례도 없다. 특히 반례가 있다면 그 길이는 이상 이하이다. 이면 답은 항상 이다.
3. 같은 접두사를 가진 금칙어를 묶는다
모든 금칙어로 트라이를 만든다. 트라이의 각 정점 가 나타내는 접두사를 라고 하고, 로 시작하는 금칙어 개수를 라 하자. 개수는 까지만 저장해도 된다. 개수가 일 때는 그 금칙어의 번호도 저장한다.
금칙어 를 고정하고, 접미사 가 어떤 금칙어의 접두사인 경우를 살펴보자.
각 금칙어의 모든 진접미사를 개별 문자열로 만들지 말고, 아호 코라식의 실패 링크를 이용하자. 의 끝 정점에서 실패 링크를 한 번 이상 따라가며 만나는 루트가 아닌 정점들은, 정확히 다른 금칙어의 접두사이기도 한 의 비어 있지 않은 진접미사들이다.
4. 남는 조각의 비교를 회전한 문자열의 검색으로 바꾼다
에서 라고 하자. 라는 조건은 , 즉 가 를 왼쪽으로 칸 회전한 문자열이라는 조건과 같다.
를 읽은 아호 코라식 상태에서 의 앞 개 문자를 차례로 추가로 읽는다. 개의 문자를 더 읽었을 때 마지막 글자는 를 왼쪽으로 칸 회전한 문자열이다. 모든 금칙어의 길이가 으로 같으므로 현재 상태가 금칙어의 끝 정점이면 일치하는 금칙어 번호를 즉시 알 수 있다. 끝 정점이 아니면 일치하는 금칙어가 없다. 실패 링크를 따라 금칙어 출력을 추가로 검색할 필요는 없다.
이를 이용하여 에 대한 회전 문자열의 금칙어 번호를 에 계산한다. 일 때 그 번호가 유일한 금칙어 번호와 같으면 두 삭제 결과가 같고, 다르면 반례를 만든다.
5. 전체 알고리즘과 정당성
실패 링크는 가능한 모든 비어 있지 않은 진접미사-접두사 겹침을 빠짐없이 열거한다. 각 겹침에서 개수에 따른 판정과 회전 문자열의 비교는 정확히 인 금칙어 쌍의 존재 여부를 판정한다. 따라서 알고리즘은 가능한 모든 반례의 겹침 길이를 정확히 찾아내며, 최소 반례의 성질에 의해 출력한 값이 정답이다.
복잡도
트라이의 정점은 최대 개이다. 알파벳 크기를 이라 하면 모든 전이를 만드는 데 시간이 걸린다. 각 금칙어의 회전 검색과 실패 링크 순회는 각각 이고, 모든 금칙어에 대한 합은 이다. 따라서 전체 시간과 공간 복잡도는 이며, 알파벳 크기가 상수이므로 이다. 재귀 호출이나 확률적 문자열 해시는 필요하지 않다.
함께 제공한 느린 풀이는 모든 순서 있는 금칙어 쌍을 직접 살펴본다. 각 쌍에서 접두사 함수로 모든 겹침을 찾고 Z 함수로 남는 조각을 비교하므로 시간이 걸린다. 이 풀이는 정답을 계산하지만 금칙어가 많은 테스트에서 시간 제한을 초과한다.
Solution written by GPT6