Z 알고리즘

Z[i] : s의 i 부터의 substring == s의 prefix 가 되는 최대 길이

 

Z 배열 :

문자열 s의 Z배열 z[i]는 s[i]에서 시작하는 부분 문자열이면서 s의 prefix이기도 한 가장 긴 문자열의 길이를 담는 배열이다.

이전에 구한 정보들을 최대한 활용해서 O(n)에 Z배열을 구할 수 있다.

 

 

문자열 ABCABCABAB인 경우 Z 배열

A	B	C	A	B	C	A	B	A	B
x	0	0	5	0	0	2	0	2	0

 

 

vector<int> z_function(const string &s) {
    int n = s.size();
    vector<int> z(n);
    z[0] = n;
    int L = 0, R = 0;
    for (int i = 1; i < n; i++) {
        if(R<i) {
            L = R = i;
            while (R<n && s[R-L] == s[R]) {
                R++;
            }
            z[i] = R-L; R--;
        }
        else {  // s[i-L...R-L] = s[i...R]
            if(i + z[i-L] -1 < R) {
                z[i] = z[i-L];   
            }
            else {
                L = i;
                while(R<n && s[R-L] == s[R]) {
                    R++;
                }
                z[i] = R-L;
                R--;
            }
        }
    }
    return z;
}

 

 

prefix과 일치하는 substring 중 가장 긴 substring의 인덱스 l,r 중 r이 가장 클 때의 l,r을 L, R에 유지한다.

 

1. R < i 

i에서 활용가능한 정보가 없기 때문에 s[0]과 s[i]에서 하나씩 비교하며 L,R을 갱신한다.

일치하는 게 없다면 L=i, R=i

일치하는게 있다면 L=i, R = i+z[i]-1

 

2. i <= R

i가 [L,R] 구간에 존재하고, s[0...R-L] == s[L...R] 이므로 s[i-L...R-L] == s[i...R].

이는 미리 앞에서 구해놓은 z[i-L]을 활용할 수 있다는 의미.

 

2.1  i + z[i-L] - 1 < R 인 경우

s[i...R] 에서 가장 길어봐야 z[i-L]인 것을 앞서 s[i-L...R-L] 의 정보를 통해서 알 수 있고 다시 구할 필요가 없음

z[i] = z[i-L]

 

2.2 i + z[i-L] - 1 >= R 인 경우

R까지는 prefix가 일치함을 알 수 있지만 R 이후로는 알 수 없으므로 R 이후의 인덱스에 대해 한 글자씩 비교한다.