Z 알고리즘과 Manacher 알고리즘

scpc를 대비하기 위해 문자열 알고리즘을 공부해 보기로 했다.

 

대표적인 문자열 알고리즘으로는 KMP, 라빈 카프 (해싱), 트라이 등이 있다. Z와 Manacher는 그에 비해서는 조금 덜 유명한 알고리즘이지만, 알아 두는 것이 좋을 것 같아 공부해 두기로 했다.

 

다음 글들을 참고하였다.

• Z
  • https://cp-algorithms.com/string/z-function.html
  • https://gina65.tistory.com/29
• Manacher
  • https://ialy1595.github.io/post/manacher/

 

Z 알고리즘

Z 알고리즘이 구하고자 하는 것은 Z array이다. 어떤 길이 $n$인 문자열 $S$의 Z array는 $S$와 $S[i:]$ (모든 접미사)의 최장 공통 접두사 길이로 정의된다. 예를 들어, $S$가 abacaba인 경우, Z array의 세 번째 원소는 abacaba와 acaba의 최장 공통 접두사 길이인 $1$이 된다.

 

Z array의 첫 번째 원소는 글마다 다르게 정의하고 있는 모습인데, 아무래도 $S$와 $S$의 최장 길이 공통 접두사라는 개념이기 때문에 별로 중요하진 않다.

 

이 글에서는 $1$-index를 기준으로 설명한다.

핵심 아이디어

KMP와 아호 코라식 등 잘 알려진 문자열 알고리즘의 핵심은 이미 계산해둔 정보를 최대한 재활용하는 것이다. "실패 함수"의 개념을 알고 있다면, 무슨 뜻인지 이해할 수 있을 것이다.

 

Z 알고리즘에서도 KMP의 실패 함수와 대단히 비슷한 접근을 통해 시간 복잡도를 줄인다. 독자가 KMP를 안다면 이해가 더 쉽겠지만, 몰라도 이해할 수 있게 설명해 보자.

 

$z[i]$를 $S$와 $S$의 $i$번 원소에서 시작하는 접미사의 최대 공통 접두사 길이로 정의하자.

 

일단 현재 우리가 $z[1] \cdots z[i-1]$까지를 전부 계산해둔 상황에서, $z[i]$를 계산한다고 가정하자. 그런데 마침 어떤 $z[j]$가 있어서, $j + z[j] - 1 \ge z[i]$라고 가정하자. 다음 그림과 같은 상황이다.

 

여기서 재미있는 생각을 해볼 수 있다. 현재 상황은 $i$가 $j$에서 시작하는 길이 $z[j]$의 접두사에 포함되는 상황이다. 그런데 배열 $z$의 정의에 의해, 해당 접두사는 $1$에서 시작하는 길이 $z[j]$의 접두사와도 같을 것이다. 그렇다면, 지금 위치 $i$를 보는 대신, $j$부터 시작하는 접두사의 위치 $i$에 대응되는, $1$부터 시작하는 접두사 (즉 전체 문자열)의 위치 $i-j+1$를 본다고 생각해도 비슷한 상황이 될 것이다.

 

구체적으로, 다음과 같은 상황을 보자.

$S$가 ababacababa, $i = 9$, $j = 7$인 경우를 생각해 보자. $z[j] = 5$를 사전에 구해 놓았고, 이제 $z[i]$를 구할 차례라고 생각하자. 그런데 생각해 보면 $j$부터 시작하는 길이 $5$의 문자열은 문자열 전체의 길이 $5$짜리 접두사와 같으므로, $z[i]$의 값을 구할 때 $z[i-j+1] = z[3]$을 참고할 수 있다. $z[3] = 3$이라는 사실을 이미 전에 구해서 알고 있을 것이다. 그렇다면 당연히 $z[i]$도 최소 $3$일 것이다.

 

위에서 본 예시는 $i$에서 시작하는 최대 공통 접두사가 $j$에서 시작하는 최대 공통 접두사와 끝이 정확히 같은 경우였다. 그러나 실제로는 끝이 더 짧거나, 끝이 더 긴 경우도 있다. 각각의 경우에 대해서 간단히 생각해 보는 것이 좋을 것이다.

 

만약 $z[i-j+1]$로 알아낸 끝이 $z[i]$의 끝보다 더 왼쪽에 있다면, 이것을 알아낸 시점에서 $z[i-j+1]$이 더 커질 수 없다는 것을 알 수 있다. 이러한 경우의 예시로 $S$가 abacabaca, $i = 7$, $j = 5$인 경우가 있다. 이 경우 $z[j] = 5$, $z[i-j+1] = z[3] = 1$이 된다. $S$와 $S[j:]$의 최장 공통 접두사가 abaca인데, $S$와 $S[i-j+1:]$의 최장 공통 접두사는 단 한 글자 a이고, 이것은 앞의 abaca에 나오는 두 번째 a에 대응된다. $z[i-j+1]$이 $1$이라는 것은 두 번째 글자부터는 일치하지 않는다는 뜻이고, 따라서 $z[i] = z[i-j+1]$로 확정된다는 것을 알 수 있다.

 

만약 $z[i-j+1]$로 알아낸 끝이 $z[i]$의 끝보다 더 오른쪽에 있다 하더라도, 그것을 신뢰할 수는 없다. 예를 들어, $S$가 ababababacababa, $i = 13$, $j = 11$인 경우를 보자. 이때 $z[i] = 5$, $z[i-j+1] = z[3] = 7$이다. 그런데 실제로 $S$와 $S[j:]$의 최장 공통 접두사 ababa의 $i-j+1 = 3$번째 글자에서 시작하는 접미사를 생각해 보면, 이 길이는 $3$일 뿐이다. 따라서 세 번째 이후의 글자부터는 $S$와 $S[j:]$가 서로 다르다는 말이 된다. 따라서 여기서부터는 $z[i-j+1]$의 값을 신뢰할 수 없게 된다.

 

여기까지 이해했다면 Z 알고리즘의 기본적인 아이디어는 모두 이해한 것이다. 다음 단락은 구현에 대한 설명이다.

구현

윗 단락에서는 $z[i]$를 구할 때 어떤 $j$가 있다고 가정만 해 두었다. 실전에서는 어떤 $j$를 잡아야 할까? $j < i$인 것들 중, $j + z[j] - 1$이 최대인 것, 즉 $j$에서 시작하는 $S$와 $S[j:]$의 최대 공통 접두사 끝점이 가장 오른쪽에 있는 것을 사용할 것이다. 이것을 사용하는 이유는, 당연히도 해당 값이 클수록 $i$ 뒤쪽 문자열에 대한 최대한 많은 정보를 담고 있기 때문이다.

 

현재까지 본 $i$ 값들 중 $j + z[j] - 1$이 최대인 것을 골라, 그 $j$ 값을 $L$, $j + z[j] - 1$의 값을 $R$이라고 하자. $i$를 키워 나가면서 $z[i]$를 구하고, 그 과정에서 $L$과 $R$이라는 포인터도 같이 업데이트해준다는 식으로 생각하면 된다.

 

몇 가지 케이스가 있다. 편의상 $S[1] \neq S[i]$인 $i$들은 그냥 스킵한다고 생각하고, 아래에서 다루는 모든 $i$에 대해 $S[i] = S[1]$이라고 생각하자.

• $i > R$: 안타깝게도, $z[i-1]$ 이전 값들로 $S[i:]$에 대한 아무런 정보도 도출할 수가 없다. 하지만, 희망적인 점은 여기서 얻을 $i + z[i] - 1$이 $R$보다 무조건 크다는 사실이다. 따라서 이 경우 우리는 그냥 나이브하게 $z[j]$를 구해도 된다. 이때 $R$이 늘어나는 횟수의 총합이 $O(n)$으로 bound되기 때문이다.
• $i \le R$, $i + z[j-i+1] - 1 < R$: 위 단락에서 설명한 케이스로, $z[j-i+1]$을 이용해 만든 $i$부터 시작하는 부분문자열이 $[L, R]$의 내부에 포함되는 케이스이다. 이 경우 $z[i] = z[j-i+1]$을 그대로 가져가면 된다.
• $i \le R$, $i + z[j-i+1] - 1 \ge R$: 부분문자열의 끝이 $R$이거나, 그 이후인 경우이다. $i + z[j-i+1] - 1$이 $R$보다 커졌더라도, $R$ 이후의 부분을 그대로 신뢰할 수 없음을 앞에서 설명했다. 다만, 만약 실제로도 $R$ 이후로 문자열이 이어지는 경우, $i > R$인 케이스에서 설명한 것과 비슷하게 나이브하게 확인해 주면 $R$이 늘어나는 횟수 총합으로 시간 복잡도를 보장하는 것이 가능하다. 따라서 이 경우 먼저 $z[i] = R - i + 1$로 설정해 주고, 더 늘릴 수 있는지 나이브하게 확인한다.

이렇게 하면 최종 시간 복잡도 $O(n)$에 문제를 해결할 수 있다.

 

다음 코드는 위와 비슷한 방식으로 구현한 Z Algorithm의 코드이다. 아래 코드는 함수형으로 구현되어 있어, 조금 더 자연스럽게 $0$-index로 구현되어 있다. 따라서 위 설명과 인덱스가 약간씩 차이나는 부분이 존재할 수 있다.

vector<int> z_array(char* str){
    int n = strlen(str);
    vector<int> z (n);
    z[0] = n;

    int L = -1, R = -1;
    for(int i=1; i<n; i++){
        if(str[0] != str[i]) continue;
        if(R < i){
            L = i, R = i;
            while(R+1 < n && str[R+1] == str[R+1-L]) R++;
            z[i] = R-L+1;
            continue;
        }
        int v = z[i-L];
        if(i+v-1 < R) z[i] = v;
        else{
            L = i;
            while(R+1 < n && str[R+1] == str[R+1-L]) R++;
            z[i] = R-L+1;
        }
    }

    return z;
}

 

Manacher 알고리즘

Manacher 알고리즘은 어떤 문자열이 있을 때 각 원소를 중심으로 가지는 가장 긴 팰린드롬의 길이를 찾는 알고리즘이다.

 

이때 팰린드롬의 중심을 기존 문자열의 원소 중 하나로 고정하면 홀수 길이 팰린드롬밖에 찾지 못하므로, 문자열의 문자 사이사이마다 더미 문자를 넣어 이러한 문제를 예방한다.

 

예를 들어, $S$가 abba인 경우, 실제로는 #a#b#b#a#와 같이 더미 문자를 넣고, $9$개 문자를 모두 가능한 중심의 후보로 고려한다. 이때 Manacher 알고리즘의 리턴 값은 $[0, 1, 0, 1, 4, 1, 0, 1, 0]$과 같게 되는데, 이는 변형된 문자열 $S'$를 기준으로 생각하면 중심점에서 양옆으로 늘릴 수 있는 최대 횟수, $S$를 기준으로 생각하면 팰린드롬의 길이가 된다.

핵심 아이디어

Manacher의 핵심 아이디어는 Z와 매우 유사하다. Z 알고리즘에서 시간을 단축한 핵심 중 하나는 $i + z[i]$ 값이 가장 큰 것을 $(L, R)$의 포인터로 관리하며, $R$이 늘어나는 횟수 제한을 통해 시간 복잡도를 보장하는 것이었다. Manacher 알고리즘도 거의 비슷한 방식으로 작동하고, 케이스 분석도 거의 똑같다. 단지 $(L, R)$이 아니라 $(mid, R)$ 꼴로, 팰린드롬의 중심과 오른쪽 끝점을 관리한다는 부분만 다를 뿐이다.

 

케이스 분석이 거의 똑같으므로 자세한 설명은 생략한다. 직접 해 보거나, 어렵다면 위 reference에 있는 글을 참고해 보자.

구현

구현은 다음과 같다.

vector<int> manacher(char* _str){
    int n = strlen(_str);
    string str;
    for(int i=0; i<n*2+1; i++) str.push_back(i%2==0 ? '#' : _str[i>>1]);

    n = n*2+1;
    vector<int> ret (n);

    int mid = -1, R = -1;
    for(int i=0; i<n; i++){
        if(i>R){
            mid = i, R = i;
            while(mid*2-R-1 >= 0 && R+1 < n && str[mid*2-R-1] == str[R+1]) R++;
            ret[mid] = R-mid;
            continue;
        }
        int v = ret[mid*2 - i];
        if(i+v < R){
            ret[i] = v;
            continue;
        }
        mid = i;
        while(mid*2-R-1 >= 0 && R+1 < n && str[mid*2-R-1] == str[R+1]) R++;
        ret[mid] = R-mid;
    }

    return ret;
}