DA.DA.S

하나의 문자열 $X$가 정해져 있다고 하자. 왼쪽부터 읽으며 주어진 문자열 중 하나가 처음으로 끝나는 순간 그 부분 문자열을 고른다. 그 뒤에서는 방금 고른 부분 문자열의 오른쪽에 있는 문자들만 대상으로 같은 과정을 반복한다. 끝나는 위치가 가장 빠른 부분 문자열부터 고르는 이 방법으로 $f(X)$를 구할 수 있다.

이 과정을 아호 코라식 자동자로 표현하자. 주어진 문자열들을 트라이에 넣고 실패 링크와 각 문자에 대한 전이를 구한다. 어떤 상태에서 주어진 문자열이 끝나는지를 표시할 때는 그 상태 자체뿐 아니라 실패 링크를 따라 도달하는 상태도 확인해야 한다. 주어진 문자열이 하나라도 끝나면 참으로 표시하며, 같은 문자열이 여러 번 주어져도 표시를 중복해서 세지 않는다.

상태 $u$에서 문자 $c$를 읽은 직후의 상태가 참으로 표시되어 있다면 부분 문자열 하나를 선택하고 루트로 돌아간다. 그렇지 않으면 그 상태에 머문다. 각각의 문자 전이가 도착할 상태와, 선택한 개수가 $1$ 증가하는지를 이 규칙으로 정한다. 루트로 돌아가는 것은 방금 선택한 부분 문자열까지 읽은 정보를 모두 버려 다음 선택과의 겹침을 막는 역할을 한다.

참으로 표시된 상태에는 머무르지 않으므로 행렬의 상태에서는 제외한다. 남은 상태 수를 $K$라 하고 $0$부터 $K-1$까지 번호를 붙이되, 루트 상태의 번호를 $0$으로 둔다.

이제 같은 길이의 모든 문자열을 한꺼번에 처리한다. $a_u$를 상태 $u$에 도달한 문자열의 개수, $z$를 그 문자열들 전체의 선택 개수 합이라고 하자. $B_{u,v}$는 상태 에서 출발하여 위 규칙에 따라 상태 로 가는 문자의 개수이고, 는 부분 문자열을 하나 선택하게 만드는 문자의 개수이다. 문자를 하나 덧붙이면

$$a'_v=\sum_{u=0}^{K-1}a_u B_{u,v},\qquad z'=26z+\sum_{u=0}^{K-1}a_u h_u$$

가 된다. 기존의 각 문자열은 문자를 덧붙이는 $26$가지 방법으로 확장되므로, 이미 얻은 선택 개수의 합 $z$에도 $26$을 곱한다.

따라서 행벡터 $(a_0,a_1,\ldots,a_{K-1},z)$에 곱할 전이 행렬을 만들 수 있다. 왼쪽 위 부분에는 를 넣고, 마지막 열의 처음 개 원소에는 를 넣는다. 마지막 행은 마지막 원소 을 제외하고 모두 이다.

빈 문자열에서는 루트에 도달하는 경우가 하나이고 선택한 부분 문자열이 없으므로 초기 벡터는 $(1,0,\ldots,0)$이다. 전이 행렬의 $M$제곱을 분할 정복으로 계산하여 초기 벡터에 곱한 뒤, 마지막 성분을 출력한다. 모든 계산은 $998\ 244\ 353$으로 나눈 나머지로 수행한다.

$L=\sum_{i=1}^{N}|S_i|$라 하면 자동자의 전체 상태 수는 $L+$ 이하이고, 참으로 표시된 상태가 적어도 하나 있으므로 이다. 시간 복잡도는 이고, 공간 복잡도는 이다.

증명

아직 선택하지 않은 문자열 구간에서 끝나는 위치가 가장 빠른 유효한 부분 문자열을 $I$라고 하자. 최대로 많은 부분 문자열을 고른 방법에서 가장 먼저 등장하는 부분 문자열을 $J$라고 하자. $I$의 끝나는 위치는 $J$의 끝나는 위치보다 오른쪽일 수 없다. 따라서 $J$를 $I$로 바꾸어도 그 뒤에 선택된 부분 문자열들과 겹치지 않는다. 부터 선택하는 최적해가 존재하므로, 그 오른쪽 구간에서도 같은 논리를 반복하면 그리디가 최적임을 알 수 있다. 유효한 부분 문자열이 없을 때에는 둘 다 아무것도 고르지 않는다.

Solution written by GPT6