접두사 함수

정의. 문자열 $s$의 접두사 함수란 배열 $p$를 말하며, 여기서 $p_i$는 문자열 $s_0 s_1 s_2 \ldots s_i$의 접두사 중 $i$번째 접두사의 접미사이기도 한 가장 긴 접두사의 길이입니다($i$번째 접두사 전체는 제외합니다).

예를 들어, 문자열 «aataataa»에서 접미사와 같은 가장 큰 접두사는 «aataa»이며, 이 문자열의 접두사 함수는 $[0, 1, 0, 1, 2, 3, 4, 5]$입니다.

vector<int> slow_prefix_function(string s) {
    int n = (int) s.size();
    vector<int> p(n, 0);
    for (int i = 1; i < n; i++)
        for (int len = 1; len <= i; len++)
            // если префикс длины len равен суффиксу длины len
            if (s.substr(0, len) == s.substr(i - len + 1, len))
                p[i] = len;
    return p;
}

이 알고리즘은 현재 $O(n^3)$에 동작하지만, 나중에 더 빠르게 개선하겠습니다.

#이것이 원래 문제를 푸는 데 어떻게 도움이 됩니까?

우선 접두사 함수를 문자열 길이에 대해 선형 시간에 계산할 수 있다고 믿고, 이를 이용해 문자열에서 부분 문자열을 찾는 방법을 배워 봅시다.

부분 문자열 $s$와 $t$를 어느 쪽에도 등장하지 않는 어떤 문자로 이어 붙입시다. 이 문자를 #로 나타내겠습니다. 그렇게 얻은 문자열 s#t의 접두사 함수를 살펴봅시다.

string s = "choose";
string t =
    "choose life. choose a job. choose a career. choose a family. choose a fu...";

cout << s + "#" + t << endl;
cout << slow_prefix_function(s + "#" + t) << endl;

choose#choose life. choose a job. choose a career. choose a family. choose a fu...
0000000123456000000012345600000000123456000100000001234560000000000012345600000000

값이 6($s$의 길이)인 모든 위치가 텍스트 $t$에서 $s$가 등장하는 위치의 끝이라는 것을 알 수 있습니다.

이러한 알고리즘(s#t에 대한 접두사 함수를 계산하고, 그 값이 $|s|$와 같은 위치를 찾는 것)을 크누스-모리스-프랫 알고리즘이라고 합니다.

#빠르게 계산하는 방법

접두사 함수의 예를 몇 가지 더 살펴보고 규칙성을 찾아봅시다:

aaaaa
01234

abcdef
000000

abacabadava
00101230101

다음과 같은 특징을 발견할 수 있습니다: $p_{i+1}$은 $p_i$보다 최대 1만큼 큽니다.

증명. 문자열 $s_{:i+1}$의 접미사와 같은 길이 $p_{i+1}$의 접두사가 있다면, 마지막 문자를 버림으로써 문자열 $s_{:i}$에 대한 올바른 접미사를 얻을 수 있으며, 그 길이는 정확히 1만큼 작습니다.

DP를 이용해 문제를 풀어 봅시다. 즉, $p_i$를 이전 값들로 나타내는 공식을 찾아봅시다.

$p_{i+1} = p_i + 1$인 것은 $s_{p_i} =s_{i+1}$인 경우이며, 오직 그 경우뿐임에 주목하십시오. 이 경우에는 $p_{i+1}$을 갱신하고 바로 다음으로 넘어가면 됩니다.

예를 들어, 문자열 $\underbrace{aabaa}t\overbrace{aabaa}$에서 접미사와 같은 최대 접두사가 표시되어 있습니다: $p_{10} = 5$. 다음 문자가 $t$와 같다면 $p_{11} = p_{10} + 1 = 6$입니다.

그런데 $s_{p_i}\neq s_{i+1}$인 경우에는 어떻게 됩니까? 같은 예시에서 다음 문자가 $t$가 아니라 $b$라고 합시다.

• $\implies$ 새 문자열의 접미사와 같은 접두사의 길이는 확실히 5보다 작습니다.
• $\implies$ 찾고 있는 새로운 접두접미사는 «aabaab»의 접미사일 뿐만 아니라, 부분 문자열 «aabaa»의 접두사이기도 합니다.
• $\implies$ 따라서 다음으로 확인할 후보는 «aabaa»의 접두사 함수 값, 즉 이미 계산해 둔 $p_4 = 2$입니다.
• $\implies$ 만약 $s_2 = s_{11}$이라면(즉, 새 문자가 후보 접두사 바로 다음에 오는 문자와 같다면) $p_{11} = p_2 + 1 = 2 + 1 = 3$입니다.

이 경우에는 실제로 그렇습니다(필요한 접두사는 «aab»입니다). 그런데 일반적인 경우에 $p_{i+1} \neq p_{p_i+1}$이라면 어떻게 해야 합니까? 그러면 같은 추론을 반복하여 길이가 더 짧은 새로운 후보 $p_{p_{p_i}}$를 얻습니다. 이 후보도 맞지 않으면 같은 방식으로 더 짧은 후보를 확인하며, 이 인덱스가 0이 될 때까지 반복합니다.

vector<int> prefix_function(string s) {
    int n = (int) s.size();
    vector<int> p(n, 0);
    for (int i = 1; i < n; i++) {
        // префикс функция точно не больше этого значения + 1
        int cur = p[i - 1];
        // уменьшаем cur значение, пока новый символ не сматчится
        while (s[i] != s[cur] && cur > 0)
            cur = p[cur - 1];
        // здесь либо s[i] == s[cur], либо cur == 0
        if (s[i] == s[cur])
            p[i] = cur + 1;
    }
    return p;
}

시간 복잡도. 최악의 경우 이 while은 한 번의 반복에서 $O(n)$번 실행될 수 있지만, 평균적으로 각 while은 $O(1)$에 동작합니다.

접두사 함수는 매 단계마다 최대 1만큼 증가하고, while의 각 반복이 끝날 때마다 최소 1만큼 감소합니다. 따라서 전체 연산 횟수는 $O(n)$을 넘지 않습니다.