C++로 문자열과 모든 접미사 간의 유사성 합계 구하기

이 문제에서는 문자열 str이 주어지며, 우리가 만들어야 할 프로그램은 이 문자열과 그 모든 접미사(suffix) 사이의 유사성(similarity) 값들의 합을 구하는 것입니다.

여기서 문자열 str의 접미사란 문자열의 앞부분 문자를 하나씩 제거하여 만들 수 있는 모든 문자열을 의미합니다.

두 문자열의 유사성은 두 문자열이 공유하는 가장 긴 접두사(prefix)의 길이로 정의됩니다. 예를 들어, str1 = 'abbac'와 str2 = 'abb'의 유사성은 3입니다.

반면 str1 = 'abca'와 str2 = 'ca'의 유사성은 0입니다. 유사성은 항상 문자열의 시작 지점부터 비교하기 때문입니다.

문제 이해를 위한 예시

입력 − str = 'xyxyx'

출력 − 9

설명 − 문자열의 모든 접미사와 각각의 유사성 값은 다음과 같습니다.

'xyxyx' -> 5
'yxyx' -> 0
'xyx' -> 3
'yx' -> 0
'x' -> 1
합계 = 5 + 0 + 3 + 0 + 1 = 9

해결 접근 방법: Z-알고리즘 활용

이 문제를 효율적으로 해결하려면 Z-알고리즘(Z-algorithm)을 사용하여 Z 배열(Z-array)을 계산하는 것이 좋습니다.

Z 배열은 원본 문자열과 같은 길이를 가지는 배열로, 각 요소는 해당 위치에서 시작하는 접미사가 문자열 전체의 접두사와 일치하는 최대 길이, 즉 최장 공통 접두사의 길이를 저장합니다.

Z[0]은 항상 문자열 전체 길이 n과 같으므로, 최종 답은 n에 Z[1]부터 Z[n-1]까지의 값을 모두 더한 값이 됩니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

void createZArray(string str, int n, int Zarray[]) {
    int L, R, k;
    L = R = 0;
    for (int i = 1; i < n; ++i) {
        if (i > R) {
            L = R = i;
            while (R < n && str[R - L] == str[R])
                R++;
            Zarray[i] = R - L;
            R--;
        }
        else {
            k = i - L;
            if (Zarray[k] < R - i + 1)
                Zarray[i] = Zarray[k];
            else {
                L = i;
                while (R < n && str[R - L] == str[R])
                    R++;
                Zarray[i] = R - L;
                R--;
            }
       }
    }
}

int calSumSimilarities(string s, int n) {
    int Zarray[n] = { 0 };
    createZArray(s, n, Zarray);
    int total = n;
    for (int i = 1; i < n; i++)
        total += Zarray[i];
    return total;
}

int main() {
    string s = "xyxyx";
    int n = s.length();
    cout<<"Sum of similarities of string with all of its suffixes is "<<calSumSimilarities(s, n);
    return 0;
}

실행 결과

Sum of similarities of string with all of its suffixes is 9

복잡도 분석

위 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도 역시 O(n)입니다. 단순히 모든 접미사를 일일이 비교하는 브루트 포스 방식(O(n²))보다 훨씬 효율적이기 때문에, 문자열 길이가 긴 경우에도 빠르게 동작합니다.