[BOJ] 5905. 악당 로봇

문제 링크

$N$개의 문자열이 주어질 때 해당 문자열들이 부분 문자열로 나오는 횟수가 가장 많은 길이가 $K$인 문자열을 만들 때 부분 문자열이 나오는 횟수를 출력하는 문제입니다.

먼저 여러개의 단어들이 주어지고 특정 문자열에서 주어진 단어들이 부분 문자열로 총 몇 번 나오는지 세는 문제를 어떻게 해결할 수 있을지 고민해 봅시다. 아마 아호-코라식을 사용해서 문제를 해결하게 되겠지요 주어진 단어들이 담긴 트라이를 만들고 주어진 문자열에 따라 노드를 순회하면서 문제를 해결하게 될껍니다. 트라이의 노드에는 실패시 이동할 노드와 해당 노드에 도착시 발견하게 되는 단어의 수를 기록해둘것이고요.

순회 방식을 생각해보면 루트 노드에서 출발하여 문자열의 각 문자에 따라 트라이를 순회하게 됩니다. 다시말해 순회 각 단계마다 트라이의 특정 노드에 위치하게 된다는 말이기도 하지요.

즉, 다음과 같은 점화식을 세울 수 있습니다.

$DP[i][node]$는 $i$번$ 이동한 상태이고 현재 위치가 $node$일 때 부분 문자열이 나타난 최대 횟수, $value[node]$는 $node$에 멈췄을 때 발견하게 되는 부문 문자열의 갯수를 의미합니다.
그리고 $next(prev, c) = node$는 $prev$노드에 위치한 상태에서 다음 문자로 $c$가 나오면 $node$노드로 이동한다는 뜻입니다.

저희가 구하고자 하는 답은 $DP[K][node]$중 가장 큰 값이므로 위 점화식을 사용하면 문제를 해결할 수 있습니다. 시간복잡도는 $O\left(KN\max\{|S_{i}|\}\right)$입니다.