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