TR;DR

z-function은 이전 결과를 재사용하여 O(N) 성능을 보장합니다.
이전 결과를 재사용할 때와 사용하지 못할 때를 구분하며 동작합니다.
상황을 구분하기 위해서 영역 [L,R] 아이디어를 사용합니다.

배경

왜 이 알고리즘 개념이 중요한가?

O(N) 성능을 보장하며 문자열열에서 패턴을 탐색할 수 있습니다.

해당 글에서 다루는 범위와 독자가 얻을 수 있는 가치는 무엇인가?

z-function알고리즘 동작을 이해할수 있습니다.
z-function알고리즘이 왜 O(N) 시간복잡도를 보장하는지 이해할 수 있습니다.

본론

핵심 개념 설명

Q. 알고리즘 입력/출력은 무엇인가?

입력 : 문자열 S
출력 : 정수 배열 z[]
- z[i] 정의는 z[i] = Max({ K : S[i...i+K] = S[0...K]}) 입니다.
- 여기서 S[0...K] = S[0]+S[1]+...+S[K-1]+S[K] 의미합니다.

언제 왜 사용하는가?(적합한 상황 또는 목적 설명)

문자열 S에 접두사 문자열 P(S[0...K]의 반복 빈도를 확인할 때
Str에서 Pattern의 반복 빈도를 확인할 때

데이터 구조와의 관계는 어떻게 되는가?

정수 배열을 사용하여, 계산된 내용을 메모하고 다음 계산에 재사용합니다.

알고리즘은 어떻게 작동되는가?(예제 또는 의사코드)

알고리즘의 핵심은 z[i]의 정의를 활용하여 이전 결과를 재사용하는 것입니다.
- z[i] = Max({ K : S[i...i+K] = S[0...K]}) 해당 정의를 활용하면,z[i] = a 일때, S[i...i+a] = S[0...a]를 만족합니다.
- 한번더 생각해보면, S[i...i+a] = S[0...a]이므로, z[1],z[2]...z[a]가 계산되었다면, z[i+1],z[i+2]...z[i+a]를 계산할때 다음 아이디어을 사용할 수 있습니다.
  - z[i+1] = Max({ K : S[i+1...i+1+K] = S[0...K]})를 계산하는 것은 z[1] = Max({ K : S[1...1+K] = S[0...K]})과 같다.
  - 왜냐하면, z[i]의 정의때문에 S[i+1] = S[1]을 추론할 수 있기기 때문입니다.
- 이러한 아이디어를 적극적으로 사용하여 계산된 결과를 재사용할 수 있습니다.
z[i]를 재사용할 수 있는지 판별하기 위해서 zBox라는 [L,R] 영역을 정의하는 추가적인 아이디어가 필요합니다.
- z[i] = a라고 해서,z[i+j] = z[j]( 0 < j <= a)을 무조건 만족하지 않습니다.
- 해당 아이디어의 유효성은 현재 i에 대해서 S[i+j...i+z[j]-1] 문자열이 S[i...i+z[i]-1]에 포함될 때 뿐입니다.
- 왜냐하면, 현재 i에 대해서 부분문자열 S[i...i+z[i]-1]이 S[0...z[i]-1]과 같다는 것을 알기 때문에 이전 결과를 재사용할 수 있기 때문입니다.
- 부분 문자열 S[i...i+z[i]-1]을 벗어나면 이전 계산 결과와 동일하다고 확신할 수 없습니다. 영역을 벗어난 상황에서 확신할 수 있는 건, S[i+j...i+z[i]-1] = S[0...z[i]-1-j] 입니다. 즉, z[i+j] => z[i]-1-j 입니다.
- 또한 영역의 끝 부분을 비교하여 i+z[j]-1 < i+z[i]-1을 만족하는지 확인해야합니다. z[j] =z[i]인 경우, S[i+z[i]-1] 이후 문자에 대해서는 불확실하기 때문입니다.
- 따라서, 확실한 영역만을 영역 [L,R]을 정의하여, i에 대해서 S[i...i+z[k]-1] ⊂ S[L...R] AND i+z[k]-1 < R을 확인하여 불확신한 상황과 확실한 상황을 구분할 수 있습니다.
  - k = i-L로 치환하였습니다.
  - 정의
    - [L,R] = {z[i]에 대하여, i = L 일때 S[L..R] = S[0...R-L] 이고, 가장 큰 R}
  - 영역 [L,R]에 대해서, L < i <= R 이고 z[i-1]까지 계산되었다면,
    - 조건을 확인하는 방법은 i+z[k]-1과 R을 비교하면 되는데요. 계산해야할 z[k]에 집중하기 위해서 z[k]와 R-i+1을 비교하겠습니다.
    - z[i]의 결과는 다음 2가지 상황에 따라 달라집니다.
    1. R-i+1 > z[k]
      - 결론적으로 z[i] = z[k]을 만족합니다.
      - 해당 상황은 S[i...i+z[k]-1]가 S[L...R]의 부분문자열이므로, S[0...R-L]이 계산되었기 때문에 S[i...R-L] != S[0...R-L-i],S[i...R-L-1] != S[0...R-L-1-i] ... S[i...z[k]] != S[0...z[k]-i]을 만족함을 증명할 수 있습니다.
      - 따라서, 이미 계산된 결과에 따라 문자 S[i+z[k]+j] !=S[z[k]+j] (j>=0 And i+z[k]+j < R)을 의미합니다.
    2. R-L+1 <= z[k]
    - 결론적으로 S[i+z[k]+j] = S[z[k]+j] (j>=0)을 만족하는지 확인하여 z[i]과 [L,R] 갱신을 검토해야합니다.
    - 해당 상황은 S[i...i+z[k]-1]가 S[L...R]의 부분 문자열 범위를 벗어나는 불확실한 상황이므로, z[i] >= R-i+1을 만족하는 상황입니다.
    - 정확한 z[i]를 계산하기 위해서는 S[i+z[k]] = S[z[k]],S[i+z[k]+1] = S[z[k]+1]...S[i+z[k]+j] = S[z[k]+j]를 확인하여, 가장 큰 j를 탐색한뒤 R-i+1+j을 z[i]에 저장하면됩니다.
    - z[i] 계산 이후, 새로운 영역 [i,i+z[i]-1]이 [L,R] 정의에 부합한지 확인하여 영역을 갱신해야합니다.
- 영역 [L,R]에 대해서, i > R이라면 z[i]`을 계산해야합니다.
  - 정의를 사용하여 z[i] = Max({ K : S[i...i+K] = S[0...K]}) 계산하고, [L,R]을 [i,i+z[i]-1]로 갱신하면 됩니다.
알고리즘의 초기 조건은 다음과 같습니다.
- 영역 [L,R] 초기값은 [0,0]으로 설정합니다.
- z[i] = 0으로 초기화합니다.
- i : 1~N 오름차순으로 계산을 진행하도록 설정합니다.
  - i = 0인 경우를 제외한 이유는 z[0] = N이라는 정보가 아이디어에 활용될 수 없고, 영역 [L,R]의 역할을 망가트리기 때문입니다.
알고리즘을 예제코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> zFunction(string s) {
    int n = s.length();
    vector<int> z(n);
    int l = 0, r = 0;

    for (int i = 1; i < n; i++) {
        if (i <= r) {
            int k = i - l;

            // Case 2: reuse the previously computed value
            z[i] = min(r - i + 1, z[k]);
        }

        // Try to extend the Z-box beyond r
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }

        // Update the [l, r] window if extended
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

시간 및 공간 시간 복잡도는 어떻게 표현되는가?

입력 문자열 S의 길이가 N일 때,
- 시간 복잡도 : O(N)
- 공간 복잡도 : O(N)
코드만 보면, 중첩 루프를 가지므로 시간 복잡도가 O(N)이 될 수 없다고 생각할 수 있습니다.
하지만 알고리즘 동작을 이해하면, O(N)이 되는 것을 이해할 수 있습니다.
1. i > r인 경우
  - 루프를 통해서 r을 갱신합니다.
  - r이 길어질 수록, 수많은 다음 i에 대해서 O(1)성능 보장합니다.
  - O(N) 성능이 됩니다.
2. i <=r인 경우
3. r-i+1 > z[k] 인 경우
  - 이전 계산 결과를 사용하여 O(1) 성능으로 z[i]을 계산합니다.
4. r-i+1 <= z[k]인 경우
  - 이전 계산 결과를 사용하여 z[i] >= r-i+1인 것을 알 수 있고, 루프를 통해서 S[i+z[i]] = S[z[i]]부터 점진적으로 매칭을 계산합니다.
  - z[i]가 계산되면 r을 갱신합니다.
  - 마찬가지로, r이 길어질 수록, 수많은 다음 i에 대해서 O(1)성능 보장합니다.
알고리즘 동작은 바깥 루프에서 N번 반복되지만, 내부 루프를 타게 되면 r이 갱신되어 다음에는 O(1) 성능이 보장됩니다.
따라서, 시간 복잡도는 r에 의존하고 r <= N-1이므로 성능은 O(N)이 됩니다.

장단점 및 제한 사항은 무엇인가?

현재 제 기준에서 알고리즘의 장점은 O(N) 성능을 보장하며 패턴 반복을 확인할 수 있다는 점입니다.
- 참고 자료에서는 KMP알고리즘보다 구현이 쉽다 라는 장점이 있지만, 제가 KMP에 대해서 모르기 때문에 판단할 수 없습니다.
알고리즘의 단점은
1. 이해가 어렵다.
- 설명을 읽으면, 이해가 되는 것 같지만, 설명하고 증명하기가 어렵습니다.
- 가장 처음에는 구체적인 문자열을 사용하여 학습을 진행하였지만, 일반화하여 설명하기가 어려웠습니다.
1. 구현 난이도
- 위에 작성된 코드는 품질이 매우 높은데요. 맨 처음에 아이디어를 사용하여 직접 구현하는 시 어려움을 격었습니다.
- 주된 원인은 알고리즘을 제대로 이해하지 못했다 라고 생각합니다.
- 경계 상황 r-i+1 = z[k] 경우와 영역 [L,R] 과 i 관계 등을 잘못 고려하여 디버깅을 하거나, 코드 품질이 나쁘게 구현하는 등의 문제가 있었습니다.
- 결론적으로 구현 난이도가 상대적으로 쉽다는 주장이 참임을 제가 판단하려면, 다른 알고리즘을 학습하고 코드를 작성해봐야 판단할 수 있겠습니다.
알고리즘의 제약사항은 문자열 1개만 입력받는다는 것인데요. 이 부분은 문자열을 합치므로써 해결할 수 있습니다.
- 문자열 pattern이 S에서 얼마나 발생하는지 확인하려면, 문자열 pattern + S를 전달하면 됩니다.
- 문자열 합치기를 응용하여 다양한 상황에 대해서 패턴 빈도를 확인할 수 있습니다.

응용 및 사례

앞에서 설명한 개념이 실제 어떻게 쓰이는가?

부분 문자열 패턴 탐색

찾아야하는 문자열 패턴 pattern과 문자열 S를 합친 pattern + S를 사용하여 패턴과 일치하는 부분문자열을 탐색할 수 있습니다.

고유한 부분문자열 탐색

z-Function를 사용하여 서로다른 z[i]의 개수를 파악하면 됩니다.

문자열 압축

정확하게 이해하지 못해서 참조로만 남겨둡니다.
추후에 학습하여 수정될 수 있습니다. (string compression)[https://cp-algorithms.com/string/z-function.html#string-compression]

비교 및 분석

유사한 알고리즘과 어떤 차이가 있는가?

KMP등의 문자열 매칭 알고리즘을 학습한 뒤에 문자열 매칭 알고리즘과의 비교를 추가할 예정입니다.
현재 깨달은 것은 해당 알고리즘이 dp를 활용한 것이며, 제게는 낯설게 dp를 활용했다는 점입니다.
- 지금까지 dp를 활용했을 때, dp[i+t] = function(dp[i],....)와같은 방식으로 이전 계산 결과만을 재사용하여 결과를 추출했는데요.
- z-Function은 상황을 구분하여 이전 결과를 재사용할 때와 새롭게 계산해야할 때 명확하게 나누었다는 것이 인상이 깊었습니다.

알고리즘을 비교한 객관적 평가 또는 실험 결과가 있는가?

해당 섹션 또한, 다른 문자열 매칭 알고리즘을 학습한 뒤에 추가할 예정입니다.

선형 성능을 보장하는 문자열 패턴 탐색 알고리즘 Z-function

TR;DR

배경

왜 이 알고리즘 개념이 중요한가?

관련 배경 지식 간단히 소개

해당 글에서 다루는 범위와 독자가 얻을 수 있는 가치는 무엇인가?

본론

핵심 개념 설명

Q. 알고리즘 입력/출력은 무엇인가?

언제 왜 사용하는가?(적합한 상황 또는 목적 설명)

데이터 구조와의 관계는 어떻게 되는가?

알고리즘은 어떻게 작동되는가?(예제 또는 의사코드)

시간 및 공간 시간 복잡도는 어떻게 표현되는가?

장단점 및 제한 사항은 무엇인가?

응용 및 사례

앞에서 설명한 개념이 실제 어떻게 쓰이는가?

관련 문제는 무엇인가?

비교 및 분석

유사한 알고리즘과 어떤 차이가 있는가?

알고리즘을 비교한 객관적 평가 또는 실험 결과가 있는가?

참조