C++로 구현하는 고유한 에코 부분 문자열(Echo Substrings) 찾기

문제 개요

문자열 S가 주어졌을 때, 어떤 문자열을 그대로 한 번 더 이어 붙인 형태(예: "abcabc" = "abc" + "abc")로 표현할 수 있는 서로 다른 비어 있지 않은 부분 문자열의 개수를 구하는 것이 목표입니다.

예를 들어 입력이 "elloelloello"라면 출력은 5가 됩니다. "elloello"("ello"+"ello"), "lloelloe"("lloe"+"lloe")처럼 절반끼리 동일한 부분 문자열들이 조건을 만족하기 때문입니다.

해결 접근 방식

모든 부분 문자열을 직접 잘라 비교하면 매우 비효율적입니다. 따라서 롤링 해시(Rolling Hash) 기법을 활용해, 인접한 두 절반의 해시값만 상수 시간에 갱신하고 비교함으로써 문제를 효율적으로 해결할 수 있습니다. 해시가 서로 같으면 두 절반이 일치한다고 판단하고, 그 결과를 집합(set)에 저장하여 중복을 자동으로 제거합니다.

prime := 31, m := 10^9 + 7 — 해시 계산에 사용할 소수와 모듈러 값입니다.
fastPow(base, power) — 분할 정복(거듭제곱의 제곱) 기법으로 모듈러 거듭제곱을 O(log power) 시간에 계산합니다.
createHashValue(s, n) — 문자열 s에 대한 다항 해시 값을 생성합니다.
recalculateHash(old, newC, oldHash, patLength) — 탐색 윈도우가 한 칸 이동할 때 맨 앞 문자를 빼고 새 문자를 더해 해시를 O(1)에 갱신합니다. 나눗셈 대신 페르마의 소정리를 이용해 fastPow(prime, m-2)로 모듈러 역원을 구해 처리합니다.
메인 로직 — 짝수 길이 i(2부터 n까지)마다 문자열을 절반으로 나눈 두 해시(hash1, hash2)를 만든 뒤, 시작 위치를 한 칸씩 밀면서 해시를 갱신하고 비교합니다. 두 해시가 같으면 ans 집합에 삽입합니다.
마지막으로 ans의 크기를 반환하면, 이것이 곧 고유한 에코 부분 문자열의 개수입니다.

각 길이별 슬라이딩 비교가 상수 시간에 처리되므로 전체 시간 복잡도는 대략 O(n²) 수준입니다. 모듈러 값을 큰 소수로 잡으면 해시 충돌 가능성은 실질적으로 무시할 수 있습니다.

구현 예시 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli prime = 31;
const lli m = 1e9 + 7;
class Solution {
    public:
    lli fastPow(lli base, lli power){
       lli res = 1;
       while (power > 0) {
          if (power & 1) {
             res = res * base;
             res %= m;
          }
          base *= base;
          base %= m;
          power >>= 1;
       }
       return res;
    }
    lli createHashValue(string s, lli n){
       lli result = 0;
       for (lli i = 0; i < n; i++) {
          result += (lli)(s[i] * fastPow(prime, i));
          result %= m;
       }
       return result;
    }
    lli recalculateHash(char old, char newC, lli oldHash, lli patLength){
       lli newHash;
       newHash = oldHash - (lli)old;
       newHash *= fastPow(prime, m - 2);
       newHash += ((lli)newC * fastPow(prime, patLength - 1));
       newHash %= m;
       return newHash;
    }
    int distinctEchoSubstrings(string text){
       int n = text.size();
       set<int> ans;
       for (int i = 2; i <= n; i += 2) {
          string temp = "";
          for (int j = 0; j < i / 2; j++) {
             temp += text[j];
          }
          int hash1 = createHashValue(temp, i / 2);
          temp = "";
          for (int j = i / 2; j < i; j++) {
             temp += text[j];
          }
          int hash2 = createHashValue(temp, i / 2);
          for (int s1 = 0, e1 = i / 2, s2 = i / 2, e2 = i; e2 < n; s1++, s2++, e1++, e2++) {
             if (hash1 == hash2) {
                ans.insert(hash1);
             }
             hash1 = recalculateHash(text[s1], text[e1], hash1, i / 2);
             hash2 = recalculateHash(text[s2], text[e2], hash2, i / 2);
          }
          if (hash1 == hash2) {
             ans.insert(hash1);
          }
       }
       return ans.size();
    }
};
main(){
    Solution ob;
    cout << (ob.distinctEchoSubstrings("elloelloello"));
}

입력

"elloelloello"