Z-algorithm 또는 Z-function은 어떠한 string s의 위치 [0, l)에서 string s와의 최대 접두어를 구하는 알고리즘이다. 작동 시간은 O(n)을 자랑한다. string에서의 문자열 검색에 O(n)의 작동시간을 가지는 알고리즘이 뭐가 있었지? 바로 KMP 알고리즘이며, KMP알고리즘을 사용하기 위해 작성하는 부분일치 테이블과 기능적으로 상당히 흡사한 측면이 있다.
CP - algorithm 사이트에서는 다음과 같이 기술 되어 있다.
The Z-function for this string is an array of length n where the i-th element is equal to the greatest number of characters starting from the position i that coincide with the first characters of s
일단 시각적인 이해를 돕기 위해서 아래의 사이트를 추천한다. 사이트를 방문해 보면 특정 문자열에 대해서 z-algorithm이 어떻게 작동하는지를 시각적으로 확인할 수 있다. 자잘한 에러가 있는 것으로 보이지만, 그것을 감안하더라도 충분히 괜찮은 사이트다.
https://personal.utdallas.edu/~besp/demo/John2010/z-algorithm.htm
Z Algorithm (JavaScript Demo)
personal.utdallas.edu
이 알고리즘의 핵심은 먼저 계산한 Z-function의 값을 이용한다는데 있다. 1번째 index부터 계산하면서 string[i]와 string[0]에서 부터 시작해서 index를 하나씩 증가시키면서 비교하는데 겹치는 부분이 없을 경우 i를 1증가 시키고, 겹치는 부분이 있다면 겹치는 부분이 없을 때까지 진행하면서 l, r(window의 left와 right)를 갱신시켜 준다. left는 현재 index, right는 겹치는 부분보다 한개 더 많은 index로 설정한다. 자 그렇다면, 현재의 index i가 l과 r 사이일 때가 관건이다. Z-function을 이용하면 아래와 같이 수식으로 결정할 수 있다.
$$ Z[i] = min(r-i, Z[i-l]) $$
이것이 어떤 의미일까? 현재의 Z[i]값이 l과 r 사이라면 이미 한번은 탐색된 구간이라는 것을 의미하고, z[i-l]은 탐색된 구간내에서의 현재 인덱스로 시작하는 substring이 s와 겹치는 갯수이고, r-i는 현재 인덱스에서 탐색된 곳까지의 남은 길이를 의미한다. 우리는 탐색된 구간을 벗어난 값을 진위 여부를 판단할 수 없다. r-i가 그것을 제한하는 역할을 한다. 이해가 어렵다면 위의 사이트에서 흐름을 한번더 살펴보길 바란다.
자, 알고리즘을 정리해 보자.
vi z_function(string s) {
int n = s.size();
vi z(n); // 최종 반환 함수, 매칭되는 접두사의 길이를 반환
z[0] = s.size();
int l=0, r=0; // 윈도우 index, left, right
for(int i=1; i<n; ++i) {
// 현재 인덱스 i에서 이전에 겹쳤던 부분이 존재한다면 z[i-l] 값과 현재 인덱스에서 겹친 부분의 마지막까지의 길이 r-i 비교
if(i<r) z[i] = min(r-i, z[i-l]);
// string의 범위내에서 z[i]와 z[i+1]의 index를 계속 비교
while(i+z[i] < n && s[z[i]] == s[i+z[i]]) {
z[i]++;
}
if(i+z[i] > r) { // 윈도우 재설정
l = i;
r = i+z[i];
}
}
return z;
}
이것을 응용한 문제는? 백준 13713, 문자열과 쿼리 문제를 추천한다. 어떻게 Z-function으로 바꾸느냐는 문자열의 방향에 주목해야 하는 것이 팁이다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
using ll = long long;
using matrix = vector<vector<ll>>;
using vi = vector<int>;
vi z_function(string s) {
int n = s.size();
vi z(n); // 최종 반환 함수, 매칭되는 접두사의 길이를 반환
z[0] = s.size();
int l=0, r=0; // 윈도우 index, left, right
for(int i=1; i<n; ++i) {
// 현재 인덱스 i에서 이전에 겹쳤던 부분이 존재한다면 z[i-l] 값과 현재 인덱스에서 겹친 부분의 마지막까지의 길이 r-i 비교
if(i<r) z[i] = min(r-i, z[i-l]);
// string의 범위내에서 z[i]와 z[i+1]의 index를 계속 비교
while(i+z[i] < n && s[z[i]] == s[i+z[i]]) {
z[i]++;
}
if(i+z[i] > r) { // 윈도우 재설정
l = i;
r = i+z[i];
}
}
return z;
}
int main() {
fastio;
string s;
cin >> s;
reverse(s.begin(), s.end());
vi z = z_function(s);
int m;
cin >> m;
while(m--) {
int idx;
cin >> idx;
cout << z[s.size()-idx] << '\n';
}
return 0;
}