쉬운 문자열 문제

문자열들을 아호-코라식 자동자에 넣는다. 자동자의 어떤 상태 $v$에 도착했을 때, 이 상태에서 끝나는 주어진 문자열의 개수를 $w_v$라고 하자. 실패 링크를 따라 끝나는 문자열도 모두 포함해야 한다. 같은 문자열이 여러 번 주어진 경우도 각각 세어야 한다.

길이 $N$의 문자열을 왼쪽부터 한 글자씩 만드는 과정을 생각하자. 현재 자동자의 상태가 $u$이고 문자 $c$를 붙였을 때 다음 상태가 $v$라면, 새로 얻는 점수는 $w_v$이다. 따라서 문제는 가중치가 있는 유한 상태 그래프에서 길이가 정확히 $N$인 경로의 최대 가중치 합을 구하는 문제가 된다.

상태 수를 $M$이라고 하자. $M \le 1+\sum |S_i|$이다. $M \times M$ 행렬 를 다음과 같이 정의한다.

$$A_{u,v}=\max(\text{상태 }u\text{에서 문자 하나를 붙여 상태 }v\text{로 갈 때 얻는 점수})$$

갈 수 없는 경우에는 $-\infty$로 둔다. 그러면 길이가 정확히 $N$인 문자열로 얻을 수 있는 최대 점수는 max-plus 곱셈에서 초기 벡터 $(0,-\infty,\ldots,-\infty)$에 $A^N$을 곱한 뒤의 최댓값이다.

max-plus 곱셈은 일반 행렬 곱셈에서 덧셈과 곱셈을 각각 최댓값과 덧셈으로 바꾼 연산이다.

$$(C=A\otimes B)_{i,j}=\max_k(A_{i,k}+B_{k,j})$$

빠른 거듭제곱을 사용하면 $O(M^3\log N)$에 답을 구할 수 있다.

점수의 최댓값은 $N \times K$ 이하이므로 $64$비트 정수에 들어간다.