นับจำนวน Substring ที่แตกต่างกัน (Distinct Substrings) ใน C++

งานคือนับจำนวน substring ที่แตกต่างกันทั้งหมดของสตริงที่กำหนด Substring คือ สตริงย่อยที่ต่อเนื่องกันของสตริงต้นฉบับ

ตัวอย่าง

ตัวอย่างที่ 1

Input: "wxyz"

Output: 10

Substrings: w, wx, wxy, wxyz, x, xy, xyz, y, yz, z

ตัวอย่างที่ 2

Input: "zzzz"

Output: 4

Substrings: z, zz, zzz, zzzz (ซ้ำกันนับครั้งเดียว)

แนวทางที่ 1: Brute Force + Hash Set (O(n²) time, O(n²) space)

สร้าง substring ทุกคู่ (i,j) ใส่ unordered_set เพื่อกรองซ้ำ

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int countDistinctSubstrings(const string& str) {
    unordered_set<string> seen;
    int n = str.length();
    
    for (int i = 0; i < n; i++) {
        string sub;
        for (int j = i; j < n; j++) {
            sub += str[j];
            seen.insert(sub);
        }
    }
    return seen.size();
}

int main() {
    string str = "aaaa";
    cout << "Distinct substrings: " << countDistinctSubstrings(str) << endl;
    return 0;
}

ผลลัพธ์

Distinct substrings: 4

แนวทางที่ 2: Suffix Array + LCP (O(n log n) time, O(n) space)

สำหรับสตริงยาว (n ~ 10⁵) วิธี brute force จะช้าเกินไป ใช้ Suffix Array และ LCP Array

สูตร: จำนวน distinct substrings = n(n+1)/2 - Σ LCP[i]

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

vector<int> buildSuffixArray(const string& s) {
    int n = s.size();
    vector<int> sa(n), rank(n), tmp(n);
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];
    }
    for (int k = 1; k < n; k <<= 1) {
        auto cmp = [&](int i, int j) {
            if (rank[i] != rank[j]) return rank[i] < rank[j];
            int ri = i + k < n ? rank[i + k] : -1;
            int rj = j + k < n ? rank[j + k] : -1;
            return ri < rj;
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++)
            tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
        rank = tmp;
    }
    return sa;
}

vector<int> buildLCP(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rank(n);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    vector<int> lcp(n-1);
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] == 0) continue;
        int j = sa[rank[i] - 1];
        while (i + h < n && j + h < n && s[i+h] == s[j+h]) h++;
        lcp[rank[i] - 1] = h;
        if (h > 0) h--;
    }
    return lcp;
}

long long countDistinctSubstringsFast(const string& s) {
    int n = s.size();
    if (n == 0) return 0;
    auto sa = buildSuffixArray(s);
    auto lcp = buildLCP(s, sa);
    long long total = 1LL * n * (n + 1) / 2;
    for (int x : lcp) total -= x;
    return total;
}

int main() {
    string str = "wxyz";
    cout << "Distinct substrings: " << countDistinctSubstringsFast(str) << endl;
    return 0;
}

ผลลัพธ์

Distinct substrings: 10

แนวทางที่ 3: Suffix Automaton (SAM) – O(n) time

มีประสิทธิภาพสูงสุด เหมาะสำหรับ n ใหญ่มาก (10⁶+)

struct State {
    int len, link;
    map<char, int> next;
};

long long countDistinctSAM(const string& s) {
    vector<State> st(2 * s.size());
    int sz = 1, last = 0;
    st[0].len = 0; st[0].link = -1;
    
    for (char c : s) {
        int cur = sz++;
        st[cur].len = st[last].len + 1;
        int p = last;
        while (p != -1 && !st[p].next.count(c)) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) st[cur].link = 0;
        else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) st[cur].link = q;
            else {
                int clone = sz++;
                st[clone] = st[q];
                st[clone].len = st[p].len + 1;
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
    
    long long ans = 0;
    for (int i = 1; i < sz; i++)
        ans += st[i].len - st[st[i].link].len;
    return ans;
}

สรุปการเลือกวิธี

โค้ดต้นฉบับมี bug

โค้ดต้นฉบับพิมพ์ str.size() แทน myset.size() ทำให้ได้ค่าผิด (สำหรับ "aaaa" ให้ 4 แทนที่จะเป็น 4 แต่ว่าเพราะ set เก็บแค่ 4 ค่า จึงตรงกันบังเอิญ)