Problems
BOJ 7719 Purify

BOJ 7719 Purify

문제 링크:

문제 내용

원본 문자열 PP와 삭제할 문자열 패턴들 NiN_i가 주어집니다. 다음의 과정을 반복하였을 때 최종적으로 남는 문자열을 출력하세요.

  • PP에서 문자열 패턴 중 하나 이상을 포함하는 가장 짧은 prefix를 선택합니다.
  • 이 prefix가 포함하는 문자열 패턴들 중에서 가장 짧은 것을 지웁니다.

입력

첫 줄에는 PP가 주어집니다. PP의 길이는 10510^5 이하입니다.

다음 줄부터는 삭제할 문자열 패턴들 NiN_i가 한 줄에 하나씩 주어집니다. NiN_i의 길이의 총합은 10510^5 이하입니다.

NiN_i의 개수는 1개 이상이며, 모든 문자열은 [0-9A-Za-z]의 글자들만을 포함합니다.

출력

문제의 정답을 출력합니다. 이는 빈 문자열이 아님이 보장됩니다.

문제 풀이

스포일러

먼저 아호-코라식을 적용합니다. 그러면 다음과 같은 풀이를 생각할 수 있습니다.

  • PP에서 글자를 하나씩 보면서, 아호-코라식에서 상태 전이를 합니다.
  • 전이한 결과 어떤 패턴을 suffix로 가진다면, 그 중 가장 짧은 것의 길이만큼을 제거하고 그 이전의 상태로 돌아갑니다.

이 풀이에는 두 가지 문제점이 있습니다.

  • 아호-코라식에서 각 위치에서 모든 매칭되는 패턴을 확인하는 데는 그러한 개수만큼의 시간이 걸립니다.
  • 상태 전이는 amortized O(1)\mathcal{O}(1)이지만, worst O(∑∣Ni∣)\mathcal{O}(\sum |N_i|)이며, 상태 전이의 결과를 되돌릴 경우 이러한 최악의 전이가 반복될 수 있습니다.

첫 번째 문제를 해결하기 위해서는 각 상태에서 매칭되는 가장 짧은 패턴의 길이를 DP로 전처리해 줄 수 있습니다.

두 번째 문제를 해결하기 위해서는 동일하게 각 상태에서 다음 글자에 따라 어느 상태로 갈 지를 DP로 전처리해 줄 수 있습니다.

메모리가 빡빡하므로, 두 번째 DP 테이블에 대해서는 정확히 ∑∣Ni∣×62\sum |N_i| \times 62개만큼의 4바이트 정수를 사용하여야 MLE를 피할 수 있습니다.

Last updated on
BOJ 7619 Restaurant tabBOJ 8129 The Invasion