Z

길이가 $n$인 문자열 $S$가 있습니다. (0-index)

이 문자열의 각 인덱스 $i$에 대해서, $S$와 부분 문자열 $S[i..n)$의 공통 최대 접두사의 길이를 구하려고 합니다.

어떻게 하면 될까요?

 

나이브하게 구하면 $O(n^2)$에 해결할 수 있습니다.

이를 $O(n)$에 구하는 Z 알고리즘에 대해 알아봅시다.

 

$S[l...r)$을 현재 $S$의 prefix와 일치하는 구간으로 정의합시다. $S[l..r) = S[0..r-l)$입니다.

초기에 $l = r = 0$입니다.

각 인덱스에 대해서 $S$와의 공통 최대 접두사의 길이를 구하면서 배열 $Z$에 저장합니다.

 

먼저 $S[0..n) = S$이므로, 첫 번째 인덱스에서 이를 구하는 것은 의미가 없습니다. 두 번째 인덱스부터 구해봅시다.

 

그럼 다음과 같이 케이스를 나눌 수 있습니다.

 

1. $i > r$

현재 얻을 수 있는 정보가 없으므로, $l = r = i$로 설정한다음, $l$번째 인덱스부터 시작하는 부분 문자열과 $S$의 접두사가 얼마나 같은지 $r$을 늘려나가면서 계산합니다. 

 

2. $i \le r$

2.1. $i + Z[i-l] \le r$

현재 $S[l..r) = S[0..r-l)$입니다. 따라서 $Z[i]$와 $Z[i-l]$는 같습니다.

2.2. $i + Z[i-l] > r$

이 경우 현재 정보를 이용해 $Z[i]$가 $r-i$보다 크거나 같다는 것까지 알 수 있고, 이 이상은 직접 계산해야 합니다.

$l = i$로 설정한 다음, 역시 $r$을 늘려나가며 접두사가 얼마나 같은지 계산하면 됩니다.

 

총 반복문을 도는데 $r$은 최대 $O(n)$번 증가하므로, 총 시간복잡도 역시 $O(n)$입니다.

 

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

13713번: 문자열과 쿼리

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int N = 1000001;
int z[N];
string s;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> s;
    reverse(s.begin(), s.end());
    // s를 뒤집으면 문제에서 구해야 하는 값이 Z배열의 값과 동일하다.
 
    int l = 0, r = 0;
    for (int i = 1; i < s.size(); i++)
    {
        if (i > r)
        {
            l = r = i;
            while (r < s.size() && s[r] == s[r - l]) r++;
            z[i] = r - l;
            r--;
        }
        else
        {
            if (i + z[i - l] <= r) z[i] = z[i - l];
            else
            {
                l = i;
                while (r < s.size() && s[r] == s[r - l]) r++;
                z[i] = r - l;
                r--;
            }
        }
    }
 
    int m; cin >> m;
    while (m--)
    {
        int i; cin >> i;
        if (i == s.size()) cout << s.size() << '\n';
        else cout << z[s.size() - i] << '\n';
    }
}

---

Z를 이용해 문자열 검색도 $O(|S|+|T|)$에 할 수 있습니다.

 

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

1786번: 찾기

역시 $S$에서 $T$를 찾으려고 합니다.

문자열 두개를 다음과 같이 합쳐 길이 $|S|+|T|+1$의 새로운 문자열을 만듭시다.

$T +$ '$' $+ S$

 

이 배열의 Z배열을 만들었을 때, $S$부분의 Z배열 값이 $T$의 길이와 같다면 $S$의 그 위치에 $T$가 있다는 뜻이 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
string S, T;
int z[2000001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    getline(cin, S);
    getline(cin, T);
 
    string s = T + '$' + S;
 
    int l = 0, r = 0;
    for (int i = 1; i < s.size(); i++)
    {
        if (i > r)
        {
            l = r = i;
            while (r < s.size() && s[r] == s[r - l]) r++;
            z[i] = r - l;
            r--;
        }
        else
        {
            if (i + z[i - l] <= r) z[i] = z[i - l];
            else
            {
                l = i;
                while (r < s.size() && s[r] == s[r - l]) r++;
                z[i] = r - l;
                r--;
            }
        }
    }
 
    vector <int> ans;
    for (int i = 0; i < S.size(); i++)
    {
        if (z[T.size() + 1 + i] == T.size()) ans.push_back(i + 1);
    }
 
    cout << ans.size() << '\n';
    for (int it : ans) cout << it << ' ';
}

---

그 외에도 Z를 이용해 접두사와 접미사를 이용하는 다양한 문제를 해결할 수 있습니다.

 

 

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217