• 0시가 되기 전에 :ac:를 받지 못해서, 백준 스트릭이 끊겼습니다. 슬프네요.
• :platinum4: 16229. 반복 패턴을 풀었습니다.
  • 어제 배웠던 z 알고리즘을 활용하면, [n-1..1] 범위의 모든 $i$에 대해서 (N-길이)가 $i$의 배수인 모든 접미사들에 대해 전체 문자열과의 공통 접두사의 길이를 $O(N\log N)$에 확인해줄 수 있습니다.
    • $\sum_{j=1}^{n}\frac{n}{j}$가 $n\log n$이라고 어디서 봤던 것 같은데, 정확하진 않습니다. 일단 $n^2$보단 작아서 시간제한 내에 돌아갑니다.
  • (N-길이)가 $i$의 배수인 모든 접미사들에 대해 공통 접두사의 길이가 $i$보다 크고, 길이가 $i$보다 작은 접미사도 문자 $k$개를 추가해서 공통 접두사의 길이를 $i$보다 크게 만들 수 있는 $i$의 최댓값을 구하면 그게 답이 됩니다.
  • $k\geq N$인 경우만 예외처리해주면 됩니다.