콘텐츠로 이동

접두사 함수. Knuth–Morris–Pratt 알고리즘

접두사 함수의 정의

길이가 $n$인 문자열 $s$가 주어집니다. 이 문자열의 접두사 함수는 길이가 $n$인 배열 $\pi$로 정의되며, 여기서 $\pi[i]$는 부분 문자열 $s[0 \dots i]$의 진접두사 중 이 부분 문자열의 접미사이기도 한 가장 긴 것의 길이입니다. 문자열의 진접두사란 그 문자열 자신과 같지 않은 접두사를 말합니다. 정의에 따라 $\pi[0] = 0$입니다.

접두사 함수의 정의를 수학적으로 쓰면 다음과 같습니다:

$$\pi[i] = \max_ {k = 0 \dots i} \{k : s[0 \dots k-1] = s[i-(k-1) \dots i] \}$$

예를 들어, 문자열 "abcabcd"의 접두사 함수는 $[0, 0, 0, 1, 2, 3, 0]$이고, 문자열 "aabaaab"의 접두사 함수는 $[0, 1, 0, 1, 2, 2, 3]$입니다.

단순한 알고리즘

접두사 함수의 정의를 그대로 따르는 알고리즘은 다음과 같습니다:

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 0; i < n; i++)
        for (int k = 0; k <= i; k++)
            if (s.substr(0, k) == s.substr(i-k+1, k))
                pi[i] = k;
    return pi;
}

이 알고리즘의 복잡도가 $O(n^3)$이라는 것은 쉽게 알 수 있으며, 개선의 여지가 있습니다.

효율적인 알고리즘

이 알고리즘은 1977년에 Knuth와 Pratt가 제안했으며, 이들과 독립적으로 Morris도 제안했습니다. 이 알고리즘은 부분 문자열 탐색 알고리즘의 핵심 함수로 사용되었습니다.

첫 번째 최적화

첫 번째로 중요한 관찰은 접두사 함수의 값이 한 번에 최대 1까지만 증가할 수 있다는 것입니다.

실제로 그렇지 않아서 $\pi[i + 1] \gt \pi[i] + 1$이라면, 위치 $i + 1$에서 끝나고 길이가 $\pi[i + 1]$인 이 접미사를 가져와 마지막 문자를 제거할 수 있습니다. 그러면 위치 $i$에서 끝나고 길이가 $\pi[i + 1] - 1$인 접미사를 얻게 되는데, 이는 $\pi[i]$보다 더 좋으므로 모순이 발생합니다.

다음 그림은 이 모순을 보여 줍니다. 위치 $i$에서 접두사이기도 한 가장 긴 진접미사의 길이는 $2$이고, 위치 $i+1$에서는 그 길이가 $4$입니다. 따라서 문자열 $s_0 ~ s_1 ~ s_2 ~ s_3$은 문자열 $s_{i-2} ~ s_{i-1} ~ s_i ~ s_{i+1}$과 같으며, 이는 문자열 $s_0 ~ s_1 ~ s_2$와 $s_{i-2} ~ s_{i-1} ~ s_i$도 같다는 뜻이므로 $\pi[i]$는 $3$이어야 합니다.

$$\underbrace{\overbrace{s_0 ~ s_1}^{\pi[i] = 2} ~ s_2 ~ s_3}_{\pi[i+1] = 4} ~ \dots ~ \underbrace{s_{i-2} ~ \overbrace{s_{i-1} ~ s_{i}}^{\pi[i] = 2} ~ s_{i+1}}_{\pi[i+1] = 4}$$

따라서 다음 위치로 이동할 때 접두사 함수의 값은 1만큼 증가하거나, 그대로 유지되거나, 어느 정도 감소할 수 있습니다. 한 단계에서 접두사 함수는 최대 1만큼만 증가할 수 있으므로, 이 사실만으로도 알고리즘의 복잡도를 $O(n^2)$으로 줄일 수 있습니다. 전체적으로 함수는 최대 $n$단계만큼 증가할 수 있으므로, 감소할 수 있는 것도 총 $n$단계뿐입니다. 즉 문자열 비교를 $O(n)$번만 수행하면 되므로, 복잡도 $O(n^2)$을 달성합니다.

두 번째 최적화

더 나아가 문자열 비교를 없애 봅시다. 이를 위해서는 이전 단계에서 계산한 모든 정보를 활용해야 합니다.

그러면 $i + 1$에 대한 접두사 함수 $\pi$의 값을 계산해 봅시다. $s[i+1] = s[\pi[i]]$이면, 위치 $i$에서 길이가 $\pi[i]$인 접미사가 길이가 $\pi[i]$인 접두사와 같다는 것을 이미 알고 있으므로 $\pi[i+1] = \pi[i] + 1$이라고 확실히 말할 수 있습니다. 이것도 예시를 통해 다시 설명합니다.

$$\underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i]} ~ \overbrace{s_3}^{s_3 = s_{i+1}}}_{\pi[i+1] = \pi[i] + 1} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_{i}}^{\pi[i]} ~ \overbrace{s_{i+1}}^{s_3 = s_{i + 1}}}_{\pi[i+1] = \pi[i] + 1}$$

그렇지 않다면, 즉 $s[i+1] \neq s[\pi[i]]$라면 더 짧은 문자열을 시도해야 합니다. 속도를 높이기 위해, 위치 $i$에서 접두사 성질이 성립하는, 즉 $s[0 \dots j-1] = s[i-j+1 \dots i]$를 만족하는 가장 긴 길이 $j \lt \pi[i]$로 곧바로 이동하고자 합니다:

$$\overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1}$$

실제로 그러한 길이 $j$를 찾으면, 다시 문자 $s[i+1]$과 $s[j]$만 비교하면 됩니다. 두 문자가 같다면 $\pi[i+1] = j + 1$을 대입할 수 있습니다. 그렇지 않다면 $j$보다 작으면서 접두사 성질이 성립하는 가장 큰 값을 찾아야 하며, 이 과정을 계속 반복합니다. 이 과정이 $j = 0$이 될 때까지 이어질 수도 있습니다. 그때 $s[i+1] = s[0]$이면 $\pi[i+1] = 1$을 대입하고, 그렇지 않으면 $\pi[i+1] = 0$을 대입합니다.

이로써 알고리즘의 전체적인 틀을 갖추었습니다. 남은 유일한 문제는 $j$에 해당하는 길이들을 어떻게 효율적으로 찾느냐는 것입니다. 다시 정리해 봅시다: 위치 $i$에서 접두사 성질이 성립하는, 즉 $s[0 \dots j-1] = s[i-j+1 \dots i]$를 만족하는 현재 길이 $j$에 대해, 접두사 성질이 성립하는 가장 큰 $k \lt j$를 찾고자 합니다.

$$\overbrace{\underbrace{s_0 ~ s_1}_k ~ s_2 ~ s_3}^j ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_k}^j ~s_{i+1}$$

그림에서 볼 수 있듯이, 이 값은 앞서 이미 계산해 둔 $\pi[j-1]$의 값이어야 합니다.

최종 알고리즘

이로써 마침내 문자열 비교를 전혀 수행하지 않고 $O(n)$번의 연산만 수행하는 알고리즘을 만들 수 있습니다.

최종 절차는 다음과 같습니다:

  • $i = 1$부터 $i = n-1$까지 반복하는 루프에서 접두사 값 $\pi[i]$를 계산합니다($\pi[0]$에는 단순히 $0$을 대입합니다).
  • 현재 값 $\pi[i]$를 계산하기 위해, $i-1$에 대한 최적의 접미사 길이를 나타내는 변수 $j$를 둡니다. 처음에는 $j = \pi[i-1]$입니다.
  • $s[j]$와 $s[i]$를 비교하여 길이 $j+1$의 접미사가 접두사이기도 한지 확인합니다. 두 문자가 같다면 $\pi[i] = j + 1$을 대입하고, 그렇지 않다면 $j$를 $\pi[j-1]$로 줄인 뒤 이 단계를 반복합니다.
  • 길이 $j = 0$에 도달했는데도 여전히 일치하지 않는다면, $\pi[i] = 0$을 대입하고 다음 인덱스 $i + 1$로 넘어갑니다.

구현

구현은 놀라울 만큼 짧고 명료합니다.

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

이 알고리즘은 온라인 알고리즘입니다. 즉, 데이터가 도착하는 대로 처리합니다. 예를 들어 문자열의 문자를 하나씩 읽으면서 즉시 처리하여, 다음 문자마다 접두사 함수의 값을 구할 수 있습니다. 이 알고리즘은 여전히 문자열 자체와 이전에 계산한 접두사 함수 값들을 저장해야 하지만, 해당 문자열에서 접두사 함수가 가질 수 있는 최댓값 $M$을 미리 알고 있다면 문자열의 처음 $M+1$개 문자와 같은 개수의 접두사 함수 값만 저장하면 됩니다.

응용

문자열에서 부분 문자열 찾기. Knuth-Morris-Pratt 알고리즘

이 문제는 접두사 함수의 고전적인 응용입니다.

텍스트 $t$와 문자열 $s$가 주어졌을 때, 텍스트 $t$에서 문자열 $s$가 나타나는 모든 위치를 찾아 출력하고자 합니다.

편의상 문자열 s의 길이를 $n$으로, 텍스트 $t$의 길이를 $m$으로 나타냅니다.

문자열 $s + \# + t$를 만듭니다. 여기서 $\#$는 $s$에도 $t$에도 나타나지 않는 구분자입니다. 이 문자열에 대해 접두사 함수를 계산해 봅시다. 이제 처음 $n + 1$개의 항목(문자열 $s$와 구분자에 해당하는 항목)을 제외한 접두사 함수 값들이 무엇을 의미하는지 생각해 봅시다. 정의에 따라 값 $\pi[i]$는 위치 $i$에서 끝나면서 접두사와 일치하는 부분 문자열의 최대 길이를 나타냅니다. 그런데 우리의 경우 이것은 $s$와 일치하면서 위치 $i$에서 끝나는 가장 큰 블록에 지나지 않습니다. 구분자 때문에 이 길이는 $n$보다 클 수 없습니다. 그러나 등식 $\pi[i] = n$이 성립한다면, 이는 문자열 $s$가 이 위치에 완전히 나타난다는 것, 즉 위치 $i$에서 끝난다는 것을 의미합니다. 다만 위치는 문자열 $s + \# + t$에서의 인덱스라는 점을 잊지 마십시오.

따라서 어떤 위치 $i$에서 $\pi[i] = n$이라면, 문자열 $t$의 위치 $i - (n + 1) - n + 1 = i - 2n$에서 문자열 $s$가 나타납니다.

접두사 함수 계산에 대한 설명에서 이미 언급했듯이, 접두사 값이 특정 값을 절대 넘지 않는다는 것을 안다면 문자열 전체와 함수 전체를 저장할 필요 없이 그 앞부분만 저장하면 됩니다. 우리의 경우 이는 문자열 $s + \#$와 그에 대한 접두사 함수 값만 저장하면 된다는 뜻입니다. 문자열 $t$를 한 번에 한 문자씩 읽으면서 접두사 함수의 현재 값을 계산할 수 있습니다.

따라서 Knuth-Morris-Pratt 알고리즘은 이 문제를 $O(n + m)$ 시간과 $O(n)$ 메모리로 해결합니다.

각 접두사의 등장 횟수 세기

여기서는 두 가지 문제를 한꺼번에 다룹니다. 길이가 $n$인 문자열 $s$가 주어집니다. 문제의 첫 번째 변형에서는 각 접두사 $s[0 \dots i]$가 같은 문자열 안에서 등장하는 횟수를 세고자 합니다. 문제의 두 번째 변형에서는 또 다른 문자열 $t$가 주어지며, 각 접두사 $s[0 \dots i]$가 $t$에서 등장하는 횟수를 세고자 합니다.

먼저 첫 번째 문제를 해결합니다. 위치 $i$에서의 접두사 함수 값 $\pi[i]$를 생각해 봅시다. 정의에 따라 이는 문자열 $s$의 길이 $\pi[i]$인 접두사가 나타나 위치 $i$에서 끝나며, 이 정의를 만족하는 더 긴 접두사는 없다는 것을 의미합니다. 동시에 더 짧은 접두사들도 이 위치에서 끝날 수 있습니다. 이것이 접두사 함수 자체를 계산할 때 이미 답했던 것과 같은 질문이라는 것은 어렵지 않게 알 수 있습니다: 위치 $i$에서 끝나는 접미사이기도 한 길이 $j$의 접두사가 주어졌을 때, 역시 위치 $i$에서 끝나는 접미사인 그다음으로 작은 접두사 $\lt j$는 무엇입니까? 따라서 위치 $i$에서는 길이 $\pi[i]$의 접두사, 길이 $\pi[\pi[i] - 1]$의 접두사, 접두사 $\pi[\pi[\pi[i] - 1] - 1]$ 등이 인덱스가 0이 될 때까지 차례로 끝납니다. 따라서 다음과 같은 방법으로 답을 계산할 수 있습니다.

vector<int> ans(n + 1);
for (int i = 0; i < n; i++)
    ans[pi[i]]++;
for (int i = n-1; i > 0; i--)
    ans[pi[i-1]] += ans[i];
for (int i = 0; i <= n; i++)
    ans[i]++;

여기서는 먼저 접두사 함수의 각 값에 대해 그 값이 배열 $\pi$에 몇 번 나타나는지 세고, 그다음 최종 답을 계산합니다: 길이 $i$인 접두사가 정확히 $\text{ans}[i]$번 나타난다는 것을 안다면, 이 수를 접두사이기도 한 그것의 가장 긴 접미사의 등장 횟수에 더해야 합니다. 마지막으로 원래의 접두사들도 세어야 하므로 각 결과에 $1$을 더해야 합니다.

이제 두 번째 문제를 생각해 봅시다. Knuth-Morris-Pratt의 기법을 적용합니다: 문자열 $s + \# + t$를 만들고 그 접두사 함수를 계산합니다. 첫 번째 과제와의 유일한 차이점은 문자열 $t$와 관련된 접두사 값, 즉 $i \ge n + 1$에 대한 $\pi[i]$에만 관심이 있다는 것입니다. 이 값들로 첫 번째 과제와 정확히 같은 계산을 수행할 수 있습니다.

문자열에 포함된 서로 다른 부분 문자열의 개수

길이가 $n$인 문자열 $s$가 주어집니다. 이 문자열에 나타나는 서로 다른 부분 문자열의 개수를 구하려고 합니다.

이 문제를 점진적으로 풀겠습니다. 즉, 현재 서로 다른 부분 문자열의 개수를 알고 있을 때 끝에 문자 하나를 추가하면 이 개수를 어떻게 다시 계산하는지 알아보겠습니다.

그러면 $s$에 있는 현재 서로 다른 부분 문자열의 개수를 $k$라 하고, $s$의 끝에 문자 $c$를 추가한다고 합시다. 당연히 $c$로 끝나는 새로운 부분 문자열이 몇 개 나타납니다. 이전에 나타나지 않았던 이 새로운 부분 문자열의 개수를 세려고 합니다.

문자열 $t = s + c$를 잡고 이를 뒤집습니다. 이제 문제는 다른 어디에도 나타나지 않는 접두사가 몇 개인지 계산하는 문제로 바뀝니다. 뒤집은 문자열 $t$의 접두사 함수의 최댓값 $\pi_{\text{max}}$를 계산하면, $s$에 나타나는 가장 긴 접두사의 길이는 $\pi_{\text{max}}$입니다. 그보다 짧은 모든 접두사도 당연히 그 안에 나타납니다.

따라서 새로운 문자 $c$를 추가할 때 새로 나타나는 부분 문자열의 개수는 $|s| + 1 - \pi_{\text{max}}$입니다.

그러므로 문자를 하나 추가할 때마다 새로운 부분 문자열의 개수를 $O(n)$ 시간에 계산할 수 있으며, 전체 시간 복잡도는 $O(n^2)$입니다.

문자를 앞에 추가하거나, 앞 또는 끝에서 문자를 삭제하는 방식으로도 서로 다른 부분 문자열의 개수를 계산할 수 있다는 점은 짚어 둘 만합니다.

문자열 압축

길이가 $n$인 문자열 $s$가 주어집니다. 이 문자열의 가장 짧은 "압축된" 표현을 찾으려고 합니다. 즉, $s$를 $t$의 복사본 하나 이상을 이어 붙인 것으로 나타낼 수 있는 가장 짧은 문자열 $t$를 찾으려고 합니다.

$t$의 길이만 찾으면 된다는 것은 분명합니다. 길이를 알면 문제의 답은 그 길이만큼의 $s$의 접두사가 됩니다.

$s$에 대한 접두사 함수를 계산합시다. 그 마지막 값을 사용하여 $k = n - \pi[n - 1]$ 값을 정의합니다. $k$가 $n$을 나누면 $k$가 답이 되고, 그렇지 않으면 효과적인 압축이 존재하지 않아 답이 $n$이 됨을 보이겠습니다.

$n$이 $k$로 나누어떨어진다고 합시다. 그러면 문자열을 길이 $k$의 블록들로 나눌 수 있습니다. 접두사 함수의 정의에 따라 길이 $n - k$의 접두사는 그 접미사와 같습니다. 그런데 이는 마지막 블록이 그 앞의 블록과 같다는 것을 의미합니다. 그리고 그 앞의 블록은 또 그 앞의 블록과 같아야 합니다. 이런 식으로 계속됩니다. 결과적으로 모든 블록이 같다는 것이 밝혀지므로, 문자열 $s$를 길이 $k$로 압축할 수 있습니다.

물론 이것이 실제로 최적임을 아직 보여야 합니다. 실제로 $k$보다 더 작은 압축이 존재한다면, 끝에서의 접두사 함수 값은 $n - k$보다 컸을 것입니다. 따라서 $k$가 실제로 답입니다.

이제 $n$이 $k$로 나누어떨어지지 않는다고 가정해 봅시다. 이 경우 답의 길이가 $n$이 된다는 것을 보이겠습니다. 귀류법으로 증명합니다. 답이 존재하고 압축된 문자열의 길이가 $p$($p$는 $n$의 약수)라고 가정합니다. 그러면 접두사 함수의 마지막 값은 $n - p$보다 커야 합니다. 즉, 접미사가 첫 번째 블록을 부분적으로 덮게 됩니다. 이제 문자열의 두 번째 블록을 살펴봅시다. 접두사와 접미사가 같고, 접두사와 접미사가 모두 이 블록을 덮으며, 둘 사이의 상대적 변위 $k$가 블록 길이 $p$의 약수가 아니므로(그렇지 않으면 $k$가 $n$의 약수가 됩니다), 블록의 모든 문자는 같아야 합니다. 그런데 그렇다면 문자열은 한 문자만 계속 반복된 것이므로 크기가 $1$인 문자열로 압축할 수 있고, 이는 $k = 1$을 의미하며 $k$는 $n$의 약수가 됩니다. 모순입니다.

$$\overbrace{s_0 ~ s_1 ~ s_2 ~ s_3}^p ~ \overbrace{s_4 ~ s_5 ~ s_6 ~ s_7}^p$$
$$s_0 ~ s_1 ~ s_2 ~ \underbrace{\overbrace{s_3 ~ s_4 ~ s_5 ~ s_6}^p ~ s_7}_{\pi[7] = 5}$$
$$s_4 = s_3, ~ s_5 = s_4, ~ s_6 = s_5, ~ s_7 = s_6 ~ \Rightarrow ~ s_0 = s_1 = s_2 = s_3$$

접두사 함수를 이용한 오토마톤 구축

구분자를 사이에 두고 두 문자열을 이어 붙이는 방법으로 돌아가 봅시다. 즉, 문자열 $s$와 $t$에 대해 문자열 $s + \# + t$의 접두사 함수를 계산합니다. $\#$는 구분자이므로 접두사 함수의 값은 당연히 $|s|$를 넘지 않습니다. 따라서 문자열 $s + \#$와 그에 대한 접두사 함수 값만 저장해 두면 충분하며, 그 뒤에 오는 모든 문자에 대한 접두사 함수는 즉석에서 계산할 수 있습니다:

$$\underbrace{s_0 ~ s_1 ~ \dots ~ s_{n-1} ~ \#}_{\text{need to store}} ~ \underbrace{t_0 ~ t_1 ~ \dots ~ t_{m-1}}_{\text{do not need to store}}$$

실제로 이러한 상황에서는 다음 문자 $c \in t$와 이전 위치의 접두사 함수 값만 알면 접두사 함수의 다음 값을 계산하기에 충분하며, 문자열 $t$의 이전 문자들이나 그 위치들에서의 접두사 함수 값은 사용할 필요가 없습니다.

다시 말해, 오토마톤(유한 상태 기계)을 구성할 수 있습니다. 이 오토마톤에서 상태는 현재 접두사 함수 값이며, 한 상태에서 다른 상태로의 전이는 다음 문자를 통해 이루어집니다.

따라서 문자열 $t$가 없어도, 전이 테이블을 계산할 때와 같은 알고리즘을 사용하여 이러한 전이 테이블 $(\text{old}_\pi, c) \rightarrow \text{new}_\pi$를 구성할 수 있습니다:

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            int j = i;
            while (j > 0 && 'a' + c != s[j])
                j = pi[j-1];
            if ('a' + c == s[j])
                j++;
            aut[i][c] = j;
        }
    }
}

그러나 이 형태에서는 알파벳 소문자에 대해 알고리즘이 $O(n^2 26)$ 시간에 동작합니다. 동적 계획법을 적용하여 테이블에서 이미 계산된 부분을 활용할 수 있다는 점에 주목하십시오. 값 $j$에서 값 $\pi[j-1]$로 이동할 때마다, 이는 사실 전이 $(j, c)$가 전이 $(\pi[j-1], c)$와 같은 상태로 이어진다는 뜻이며, 이 답은 이미 정확하게 계산되어 있습니다.

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            if (i > 0 && 'a' + c != s[i])
                aut[i][c] = aut[pi[i-1]][c];
            else
                aut[i][c] = i + ('a' + c == s[i]);
        }
    }
}

결과적으로 오토마톤을 $O(26 n)$ 시간에 구성합니다.

이러한 오토마톤은 언제 유용합니까? 우선, 문자열 $s + \# + t$에 대한 접두사 함수와 그 값들은 주로 한 가지 목적, 즉 문자열 $t$에서 문자열 $s$가 나타나는 모든 위치를 찾는 데 사용된다는 점을 기억하십시오.

따라서 이 오토마톤의 가장 분명한 이점은 문자열 $s + \# + t$에 대한 접두사 함수 계산의 가속입니다. $s + \#$에 대한 오토마톤을 구축하면 더 이상 문자열 $s$나 그에 대한 접두사 함수 값을 저장할 필요가 없습니다. 모든 전이는 이미 테이블에 계산되어 있습니다.

그러나 덜 분명한 두 번째 활용법도 있습니다. 문자열 $t$가 어떤 규칙에 따라 구성된 거대한 문자열일 때 오토마톤을 사용할 수 있습니다. 예를 들어 Gray 문자열이나, 입력으로 주어진 여러 짧은 문자열을 재귀적으로 조합하여 만든 문자열이 이에 해당합니다.

완결성을 위해 다음과 같은 문제를 풀어 보겠습니다: 수 $k \le 10^5$와 길이가 $\le 10^5$인 문자열 $s$가 주어집니다. $k$번째 Gray 문자열에서 $s$가 나타나는 횟수를 계산해야 합니다. Gray 문자열은 다음과 같이 정의된다는 것을 떠올려 보십시오:

$$\begin{align} g_1 &= \text{"a"}\\ g_2 &= \text{"aba"}\\ g_3 &= \text{"abacaba"}\\ g_4 &= \text{"abacabadabacaba"} \end{align}$$

이런 경우에는 문자열 $t$의 길이가 천문학적이기 때문에 이 문자열을 구성하는 것조차 불가능합니다. $k$번째 그레이 문자열의 길이는 $2^k-1$자입니다. 그러나 문자열 시작 지점의 접두사 함수 값만 알면 문자열 끝 지점의 접두사 함수 값을 효율적으로 계산할 수 있습니다.

오토마톤 자체와 더불어, 상태 $j$에서 시작하여 문자열 $g_i$를 처리한 후의 오토마톤 값인 $G[i][j]$도 계산합니다. 그리고 추가로, 상태 $j$에서 시작하여 $g_i$를 처리하는 동안 $g_i$에서 $s$가 등장하는 횟수인 $K[i][j]$도 계산합니다. 실제로 $K[i][j]$는 연산을 수행하는 동안 접두사 함수가 값 $|s|$를 가진 횟수입니다. 그러면 문제의 답은 $K[k][0]$이 됩니다.

이 값들을 어떻게 계산할 수 있겠습니까? 먼저 기본값은 $G[0][j] = j$와 $K[0][j] = 0$입니다. 그리고 이후의 모든 값은 이전 값들과 오토마톤을 사용하여 계산할 수 있습니다. 어떤 $i$에 대한 값을 계산하려면, 문자열 $g_i$가 $g_{i-1}$, 알파벳의 $i$번째 문자, 그리고 $g_{i-1}$로 이루어져 있다는 점을 떠올리면 됩니다. 따라서 오토마톤은 다음 상태로 이동합니다:

$$\text{mid} = \text{aut}[G[i-1][j]][i]$$
$$G[i][j] = G[i-1][\text{mid}]$$

$K[i][j]$의 값들도 쉽게 셀 수 있습니다.

$$K[i][j] = K[i-1][j] + (\text{mid} == |s|) + K[i-1][\text{mid}]$$

이렇게 하여 그레이 문자열에 대한 문제를 풀 수 있으며, 마찬가지로 이와 비슷한 수많은 다른 문제도 풀 수 있습니다. 예를 들어 완전히 같은 방법으로 다음 문제도 풀 수 있습니다: 문자열 $s$와 몇 개의 패턴 $t_i$가 주어지며, 각 패턴은 다음과 같이 지정됩니다: 패턴은 일반 문자들로 이루어진 문자열이며, 그 안에 $t_k^{\text{cnt}}$ 형태로 이전 문자열들이 재귀적으로 삽입될 수 있습니다. 이는 해당 위치에 문자열 $t_k$를 $\text{cnt}$번 삽입해야 한다는 뜻입니다. 이러한 패턴의 예는 다음과 같습니다:

$$\begin{align} t_1 &= \text{"abdeca"}\\ t_2 &= \text{"abc"} + t_1^{30} + \text{"abd"}\\ t_3 &= t_2^{50} + t_1^{100}\\ t_4 &= t_2^{10} + t_3^{100} \end{align}$$

재귀적 치환으로 인해 문자열이 크게 불어나서, 그 길이가 $100^{100}$ 정도에 이를 수 있습니다.

각 문자열에서 문자열 $s$가 등장하는 횟수를 구해야 합니다.

이 문제도 같은 방식으로, 접두사 함수의 오토마톤을 구성한 뒤 이전 결과를 이용하여 각 패턴에 대한 전이를 계산함으로써 풀 수 있습니다.

연습 문제