BOJ 10745 Censoring
BOJ 10745 Censoring
문제 내용
원본 문자열 와 삭제할 문자열 패턴들 가 주어집니다. 다음의 과정을 반복하였을 때 최종적으로 남는 문자열을 출력하세요.
- 에 등장하는 문자열 패턴들 중에서 시작 위치가 가장 빠른 것을 선택하여 지웁니다.
삭제할 문자열 패턴들 중에는 다른 문자열 패턴의 부분 문자열인 것이 없음이 보장됩니다.
입력
첫 줄에는 가 주어집니다. 의 길이는 이하입니다.
다음 줄에는 삭제할 문자열 패턴들의 개수 이 주어집니다.
그 다음 줄에는 삭제할 문자열 패턴들 가 한 줄에 하나씩 주어집니다. 의 길이의 총합은 이하입니다.
의 개수는 1개 이상이며, 모든 문자열은 [a-z]의 글자들만을 포함합니다.
출력
문제의 정답을 출력합니다. 이는 빈 문자열이 아님이 보장됩니다.
문제 풀이
스포일러
이 풀이는 #7719 Purify 의 풀이를 복사한 것입니다.
먼저 아호-코라식을 적용합니다. 그러면 다음과 같은 풀이를 생각할 수 있습니다.
- 에서 글자를 하나씩 보면서, 아호-코라식에서 상태 전이를 합니다.
- 전이한 결과 어떤 패턴을 suffix로 가진다면, 그 중 가장 짧은 것의 길이만큼을 제거하고 그 이전의 상태로 돌아갑니다.
이 풀이에는 두 가지 문제점이 있습니다.
- 아호-코라식에서 각 위치에서 모든 매칭되는 패턴을 확인하는 데는 그러한 개수만큼의 시간이 걸립니다.
- 상태 전이는 amortized 이지만, worst 이며, 상태 전이의 결과를 되돌릴 경우 이러한 최악의 전이가 반복될 수 있습니다.
첫 번째 문제를 해결하기 위해서는 각 상태에서 매칭되는 가장 짧은 패턴의 길이를 DP로 전처리해 줄 수 있습니다.
두 번째 문제를 해결하기 위해서는 동일하게 각 상태에서 다음 글자에 따라 어느 상태로 갈 지를 DP로 전처리해 줄 수 있습니다.
Last updated on