DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

금칙어 필터의 버그

문제로 돌아가기

해설

전체 금칙어 길이의 합을 L=NML=NML=NM이라고 하자.

1. 두 금칙어가 겹치는 경우

어떤 금칙어 AAA의 비어 있지 않은 진접미사와 다른 금칙어 BBB의 진접두사가 같은 문자열 YYY라고 하자. AAA와 BBB는 같은 금칙어여도 된다. k=∣Y∣k=|Y|k=∣Y∣라 놓으면 1≤k<M1\leq k<M1≤k<M이고, 다음과 같이 나타낼 수 있다.

A=XY,B=YZ,∣X∣=∣Z∣=M−k.A=XY,\qquad B=YZ,\qquad |X|=|Z|=M-k.A=XY,B=YZ,∣X∣=∣Z∣=M

메시지 XYZXYZXYZ에서 앞의 AAA를 지우면 ZZZ, 뒤의 BBB를 지우면 XXX가 남는다. 두 문자열의 길이는 모두 MMM보다 작으므로 더 삭제할 수 없다. 따라서 이면 는 반례이며, 그 길이는 이다. 반대로 이면 이 두 삭제는 같은 문자열을 만든다.

2. 최소 반례에는 겹치는 두 금칙어만 있으면 된다

처리 결과가 달라지는 메시지가 존재한다고 가정하고, 그중 길이가 가장 짧은 것을 SSS라고 하자. SSS보다 짧은 모든 메시지의 처리 결과는 하나로 정해진다.

SSS에서 가능한 첫 삭제들을 살펴보자. 첫 삭제 후의 문자열들은 모두 SSS보다 짧으므로 각각의 처리 결과가 유일하다. SSS에는 서로 다른 처리 결과가 있으므로, 이후의 처리 결과가 서로 다른 두 첫 삭제를 고를 수 있다.

두 삭제 구간이 같다면 한 번 삭제한 문자열도 같으므로 모순이다. 두 구간이 겹치지 않는다면 한쪽을 삭제한 후 다른 쪽도 삭제하여 같은 문자열에 도달할 수 있다. 첫 삭제 후의 처리 결과는 각각 유일하므로 이 경우에도 최종 결과가 같아져 모순이다.

따라서 두 삭제 구간은 일부 겹친다. 그 합집합을 XYZXYZXYZ로 나타내면 두 금칙어는 XYXYXY와 YZYZYZ이다. X=ZX=ZX=Z이면 두 첫 삭제 직후의 전체 문자열이 같아지므로 역시 모순이다. 그러므로 X≠ZX\neq Z이고, 앞 절에 의해 합집합 자체가 반례이다. 그 길이는 이하이다.

따라서 정답은 X≠ZX\neq ZX=Z인 모든 겹침에 대한 2M−k2M-k2M−k의 최솟값이다. 그런 겹침이 없으면 반례도 없다. 특히 반례가 있다면 그 길이는 M+1M+1M+1 이상 이하이다. 이면 답은 항상 이다.

3. 같은 접두사를 가진 금칙어를 묶는다

모든 금칙어로 트라이를 만든다. 트라이의 각 정점 vvv가 나타내는 접두사를 YYY라고 하고, YYY로 시작하는 금칙어 개수를 c(v)c(v)c(v)라 하자. 개수는 222까지만 저장해도 된다. 개수가 111일 때는 그 금칙어의 번호도 저장한다.

금칙어 A=XYA=XYA=XY를 고정하고, 접미사 YYY가 어떤 금칙어의 접두사인 경우를 살펴보자.

  • c(v)≥2c(v)\geq2c(v)≥2이면 YYY로 시작하는 서로 다른 금칙어 YZ1,YZ2YZ_1,YZ_2YZ1​,YZ가 있다. 두 금칙어가 서로 다르므로 이고, 적어도 하나는 와 다르다. 따라서 이 겹침 길이 에서는 반드시 반례를 만들 수 있다.

각 금칙어의 모든 진접미사를 개별 문자열로 만들지 말고, 아호 코라식의 실패 링크를 이용하자. AAA의 끝 정점에서 실패 링크를 한 번 이상 따라가며 만나는 루트가 아닌 정점들은, 정확히 다른 금칙어의 접두사이기도 한 AAA의 비어 있지 않은 진접미사들이다.

4. 남는 조각의 비교를 회전한 문자열의 검색으로 바꾼다

A=XYA=XYA=XY에서 d=∣X∣=M−kd=|X|=M-kd=∣X∣=M−k라고 하자. X=ZX=ZX라는 조건은 , 즉 가 를 왼쪽으로 칸 회전한 문자열이라는 조건과 같다.

AAA를 읽은 아호 코라식 상태에서 AAA의 앞 M−1M-1M−1개 문자를 차례로 추가로 읽는다. ddd개의 문자를 더 읽었을 때 마지막 MMM글자는 AA를 왼쪽으로 칸 회전한 문자열이다. 모든 금칙어의 길이가 으로 같으므로 현재 상태가 금칙어의 끝 정점이면 일치하는 금칙어 번호를 즉시 알 수 있다. 끝 정점이 아니면 일치하는 금칙어가 없다. 실패 링크를 따라 금칙어 출력을 추가로 검색할 필요는 없다.

이를 이용하여 d=0,1,…,M−1d=0,1,\ldots,M-1d=0,1,…,M−1에 대한 회전 문자열의 금칙어 번호를 O(M)O(M)O(M)에 계산한다. c(v)=1c(v)=1c(일 때 그 번호가 유일한 금칙어 번호와 같으면 두 삭제 결과가 같고, 다르면 반례를 만든다.

5. 전체 알고리즘과 정당성

  • 트라이를 만들면서 접두사별 금칙어 개수와 금칙어 번호를 기록한다.
  • 너비 우선 탐색으로 아호 코라식의 실패 링크와 모든 문자 전이를 만든다.
  • 각 금칙어 AAA에 대해 회전 문자열의 일치 번호를 계산한다.
  • AAA의 끝 정점의 실패 링크부터 루트 직전까지 따라간다. 깊이가 kkk인 정점에서 접두사별 개수가 222 이상이거나, 유일한 금칙어 번호와 M−kM-kM−k칸 회전의 일치 번호가 다르면 를 후보로 기록한다.

실패 링크는 가능한 모든 비어 있지 않은 진접미사-접두사 겹침을 빠짐없이 열거한다. 각 겹침에서 개수에 따른 판정과 회전 문자열의 비교는 정확히 X≠ZX\neq ZX=Z인 금칙어 쌍의 존재 여부를 판정한다. 따라서 알고리즘은 가능한 모든 반례의 겹침 길이를 정확히 찾아내며, 최소 반례의 성질에 의해 출력한 값이 정답이다.

복잡도

트라이의 정점은 최대 L+1L+1L+1개이다. 알파벳 크기를 σ=26\sigma=26σ=26이라 하면 모든 전이를 만드는 데 O(σL)O(\sigma L)O(σL) 시간이 걸린다. 각 금칙어의 회전 검색과 실패 링크 순회는 각각 O(M)O(M)O(M이고, 모든 금칙어에 대한 합은 이다. 따라서 전체 시간과 공간 복잡도는 이며, 알파벳 크기가 상수이므로 이다. 재귀 호출이나 확률적 문자열 해시는 필요하지 않다.

함께 제공한 느린 풀이는 모든 순서 있는 금칙어 쌍을 직접 살펴본다. 각 쌍에서 접두사 함수로 모든 겹침을 찾고 Z 함수로 남는 조각을 비교하므로 O(N2M)O(N^2M)O(N2M) 시간이 걸린다. 이 풀이는 정답을 계산하지만 금칙어가 많은 테스트에서 시간 제한을 초과한다.

Solution written by GPT6

−
k.
X≠ZX\neq Z
X=Z
XYZXYZXYZ
2M−k2M-k2M−k
X=ZX=ZX=Z
X
=
Z
XYZXYZXYZ
∣S∣|S|∣S∣
2M−12M-1
2M−1
M=1M=1M=1
−1-1−1
2​
Z1≠Z2Z_1\neq Z_2Z1​=Z2​
XXX
k=∣Y∣k=|Y|k=∣Y∣
  • c(v)=1c(v)=1c(v)=1이면 유일한 금칙어 B=YZB=YZB=YZ에 대해 X=ZX=ZX=Z인지 확인하면 된다.
  • =
    Z
    B=YXB=YXB=YX
    BBB
    AAA
    ddd
    A
    ddd
    MMM
    v
    )
    =
    1
    kk
    k
  • 기록한 kkk의 최댓값을 KKK라 할 때 2M−K2M-K2M−K를 출력한다. 후보가 없으면 −1-1−1을 출력한다.
  • )
    O(NM)=O(L)O(NM)=O(L)O(NM)=O(L)
    O(σL)O(\sigma L)O(σL)
    O(L)O(L)O(L)