블로그 옮겼습니다

Z algorithm 본문

Algorithm/Algorithms

Z algorithm

sgc109 2017. 9. 8. 15:38

Z algorithm 은 문자열관련 알고리즘이다.  우선 Z Array 라는 것이 있다. Z[i] 의 정의는 아래와 같다.

Z[i] : S[i...] 의 prefix 들 중 S의 prefix이기도 한 녀석들 중 길이가 가장 긴녀석의 길이

즉, i에서 시작하는 S의 부분 문자열들 중 S의 prefix 이기도 한 녀석들 중 가장 긴 길이이다.

이 Z Array 를 O(|S|) 의 시간에 구할 수 있게 해주는 것이 Z algorithm 이다.

우선 이 것을 알면 KMP와 같이 문자열 검색이 선형시간에 가능하다.

즉, 어떤 긴 문자열 S에서 특정 패턴 P가 등장하는 위치를 모두 구하는 것이 

Z 알고리즘을 활용하여 O(S + P) 에 가능한데 이 방법은 나중에 아래에서 설명하겠다.

그리고 가끔 이런 문제들이 있다.

'어떤 문자열 S가 주어질 때 S의 prefix 이면서 suffix 인 문자열 중에 어쩌고 저쩌고 블라블라..........'

이런 문제에서 엄청난 힘을 발휘한다. 


아무튼 이제 Z Array 를 어떻게 O(|S|) 에 구할 수 있을까?

우선 naive 하게 생각해보면 각각의 인덱스 i 에 대해 Z[i] 를 구하는 직관적인 방법은 

S[0] 와 S[i] 가 같은지 비교하고

S[1] 와 S[i + 1] 가 같은지 비교하고...

이것을 같지않을 때까지 반복하는 것이다. 이 방법으로 하면 문자열의 길이가 N이라고 할 때

\(O(N^2)\) 이 걸릴 것이다. 그러면 이것을 \(O(N)\) 로 줄여보자.

일단 prefix 이기도 한 substring 을 prefix-substring 이라고 표현하겠다.

우선 L과 R이라는 것을 유지하자. L과 R이 뭐냐면

특정 위치 i에서의 prefix-substring 중 가장 긴 것을 구했을 때 그 substring 의

왼쪽 인덱스 l과 오른쪽 인덱스 r아 나올 텐데 이들 중에서 r이 가장 큰 것의 l과 r을 L과 R에 유지하는 것이다.

그럼 L과 R이 있고 현재 Z Array 의 i번째 값을 구한다고 해보자. 그럼 케이스를 두가지로 나눌 수가 있다.

1. \(R \lt {i}\)

이 때는 그냥 S[0]와 S[i] 부터 시작해서 차례로 한글자씩 비교해나간다. 만약 prefix-substring 이 존재한다면

그 오른쪽 인덱스인 r로 R이 갱신(증가)될 것이고(물론 L도 l로 갱신)

존재하지않는다면 딱 한번의 비교만 하고 Z[i] 는 0이되면서 i를 1 증가시킬것이다.


2. \(L \le {i} \le {R}\)

(i가 절대 L보다 작아질수 없다는 것은 자명하다)

이 때에는 S[0] 부터 비교하지 않아도 기존의 정보를 활용하여 빠르게 Z[i]를 구할 수가 있다.

 

L과 R이 있다는 것은 위 그림에서 S[L...R] 인 W와 정확하게 같은 prefix 인 W' 가 있다는 것이기 때문에

S[i...R] 과 같은 S[i'...R'] 가 있다는 뜻이고 만약 그렇다면 Z[i'] 를 K라고 할 때 두가지 케이스로 나뉜다.

1) \(K\lt{R - i}\) 인 경우

S[i'...i'+K-1] == S[i...i+K-1] 고, S[i'+K] == S[i+K] 이기때문에 S[i'+K] != S[K] 면 S[i+K] != S[K] 라는것을

알 수 있기 때문에 Z[i] 또한 K라는 것을 알 수가 있다.

2) \({R - i}\le{K}\) 인 경우

우선 위에서도 말했듯이 S[i'...R'] == S[i...R] 이기 때문에 일단 확실한건 Z[i] 는 최소한 R - i + 1은 된다는 것이다.

하지만 문제는 S[R'+x] == S[R+x] (x > 0) 인지는 보장할 수가 없다. 왜냐면 위에서 말했듯 S[i...R] 와 S[i'...R'] 가 같다는

것만 아는 상태이기 때문이다. 그렇기 때문에 이 때는 일단 S[...R-i] == S[i...R] 인건 알수있으므로 그다음부터

틀릴 때까지 한 문자씩 비교하면서 직접 비교해주면된다. 그럼 R이 마지막으로 맞은 인덱스로 갱신이 되면서

(물론 L도 i로 갱신) 증가한다.

위의 \(L\le{i}\le{R}\) 의 경우던, \(R\lt{i}\) 의 경우던간에 새롭게 비교하는 문자의 인덱스는 R보다 큰 위치이고

마지막으로 비교한 위치로 R이 갱신되는 것이 반복되기 때문에 비교는 O(N) 번밖에 하지 않는 다는 것을 알 수가

있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int Z[1000003], L, R;
int main() {
    fastio();
    string S;
    cin >> S;
    int N = sz(S);
    for (int i = 1; i < N; i++) {
        if (i > R) {
            L = R = i;
            while (R < N && S[R - L] == S[R]) R++;
            Z[i] = R - L; R--;
        } else {
            int k = i - L;
            if (Z[k] < R - i + 1) Z[i] = Z[k];
            else {
                L = i;
                while (R < N && S[R - L] == S[R]) R++;
                Z[i] = R - L; R--;
            }
        }
    }
    return 0;
}
cs

 

그럼 이 알고리즘으로 문자열 S에서 특정 패턴 P가 등장하는 모든 곳을 O(S + P) 에 구하는 방법을 알아보자.

우선 S' = P$S 의 형태로 새로운 문자열을 만든다. 여기서 $는 P와 S 모두에 포함되지 않는 임의의 문자이다.

이렇게 하여 S' 의 Z Array 를 구하고, Z[i] = |P| 가 모든 i를 구한뒤 각각에 |P| + 1 를 빼주면

우리가 구하고자 하는 것이 나온다. 왜 그런걸까? 우선 $문자의 왼쪽부분은 Z[i] 가 무조건 |P| 보다 작다는 것을

알 수 있다. 왜냐하면 중간에 $문자가 껴있기 때문이다. 그리고 모든 Z[i] 는 |P| 보다 커질 수 없다는 것도 알 수가 있다.

왜냐하면 prefix 의 길이가 |P| + 1 이되는 순간 $문자가 껴버리기 때문이다. 그렇기 때문에

$문자의 오른쪽인 i에 대해 Z[i] 가 |P| 가 된다면 S'[i...i+|P|-1] == S[...|P|-1] 이라는 것이기 때문에

i에서 패턴이 등장했다는 것을 알 수가 있고 i를 실제 S에서의 인덱스를 구하려면 |P| + 1 만큼 빼주면 되기 때문에

Z Array 를 O(S + P) 에 계산하고 O(S) 로 Z[i] = |P| 인 부분의 위치를 모두 찾으면 끝이다.


(Z algorithm 연습문제)

http://codeforces.com/contest/535/problem/D     풀이


('prefix 면서 suffix 인 문자열 어쩌구 저쩌구....' 에 관한 문제들)

https://www.acmicpc.net/problem/13506

https://www.acmicpc.net/problem/13576

Comments