hckim

문제링크

https://www.acmicpc.net/problem/1605

풀이

• 반복 부분문자열의 길이의 최대는 max(lcp[i]) 이다.

코드

• 시간복잡도: $O(Nlog^2N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    auto buildSA = [&](string& s) {
        int N = s.size();
        vector<int> sa(N, 0), r(2 * N, 0), nr(2 * N, 0);
        for (int i = 0; i < N; ++i) {
            sa[i] = i;
            r[i] = s[i];
        }
        for (int d = 1; d < N; d <<= 1) {
            auto cmp = [&](int i, int j) {
                return r[i] < r[j] || (r[i] == r[j] && r[i + d] < r[j + d]);
            };
            sort(all(sa), cmp);
            nr[sa[0]] = 1;
            for (int i = 1; i < N; ++i) {
                nr[sa[i]] = nr[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
            }
            r = nr;
        }
        return sa;
    };

    auto buildLCP = [&](string& s) {
        int N = s.size();
        auto sa = buildSA(s);
        vector<int> lcp(N), isa(N);
        for (int i = 0; i < N; ++i) {
            isa[sa[i]] = i;
        }
        for(int k = 0, i = 0;i < N;++i) {
            if(isa[i]){
                for(int j = sa[isa[i]-1]; max(i, j) + k < N && s[i+k] == s[j+k]; ++k);
                lcp[isa[i]] = (k ? k-- : 0);
            }
        }
        return lcp;
    };

    int L;
    cin >> L;
    string s;
    cin >> s;

    auto lcp = buildLCP(s);

    cout << *max_element(lcp.begin() + 1, lcp.end());
}

문제링크

https://www.acmicpc.net/problem/11479

풀이

• 문자열의 서로 다른 부분 문자열 = 모든 접미사의 접두사
• 각 접미사에 대해 lcp 상의 앞 인덱스에 있는 접미사와 겹치는 접두사부분 길이만큼이 중복
• $ans = \frac{N(N + 1)}{2} - \sum_{i = 1}^{N - 1} lcp[i]$

코드

• 시간복잡도: $O(Nlog^2N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    auto buildSA = [&](string& s) {
        int N = s.size();
        vector<int> sa(N), r(2 * N, 0), nr(2 * N, 0);
        for (int i = 0; i < N; ++i) {
            sa[i] = i;
            r[i] = s[i];
        }
        for (int d = 1; d < N; d <<= 1) {
            auto cmp = [&](int i, int j) {
                return r[i] < r[j] || (r[i] == r[j] && r[i + d] < r[j + d]);
            };
            sort(all(sa), cmp);
            nr[sa[0]] = 1;
            for (int i = 1; i < N; ++i) {
                nr[sa[i]] = nr[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
            }
            r = nr;
        }
        return sa;
    };

    auto buildLCP = [&](string& s) {
        int N = s.size();
        auto sa = buildSA(s);
        vector<int> lcp(N, 0), isa(N);
        for (int i = 0; i < N; ++i) {
            isa[sa[i]] = i;
        }
        for(int k = 0, i = 0;i < N;++i) {
            if(isa[i]){
                for(int j = sa[isa[i]-1]; max(i, j) + k < N && s[i+k] == s[j+k]; ++k);
                lcp[isa[i]] = (k ? k-- : 0);
            }
        }
        return lcp;
    };

    auto lcp = buildLCP(s);
    long long N = s.size();
    long long ans = N * (N + 1) / 2;
    for (int i = 1; i < N; ++i) {
        ans -= lcp[i];
    }
    cout << ans << '\n';
}

문제링크

https://www.acmicpc.net/problem/9248

풀이

• SA 구하기
  • suffix 들을 앞부분 길이 1, 2, 4, 8 ... 에 대해서 정렬
  • 앞부분 길이 d 에서 정렬한 정보를 2 * d 를 정렬할 때 이용할 수 있음
• LCP 구하기 (Kasai's algorithm)
  • 인덱스 0 시작, 1시작, ... 접미사들에 대해서 차례로 lcp 를 구한다
  • $lcp[isa[i]] = k$ 이면 $lcp[isa[i + 1]] \geq k - 1$ 임을 이용한다

코드

• 시간복잡도
  • 문자열길이: $N$ 
  • SA: $O(Nlog^2N)$
    • counting sort 로 정렬시 $O(NlogN)$
  • LCP: $O(O(SA) + N)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    string s;
    cin >> s;

    auto buildSA = [&](string& s) {
        int N = s.size();
        vector<int> sa(N), r(2 * N, 0), nr(2 * N);
        for (int i = 0; i < N; ++i) {
            sa[i] = i;
            r[i] = s[i];
        }

        for (int d = 1; d < N; d <<= 1) {
            auto cmp = [&](int i, int j) {
                return r[i] < r[j] || (r[i] == r[j] && r[i + d] < r[j + d]);
            };
            sort(all(sa), cmp);
            nr[sa[0]] = 1;
            for (int i = 1; i < N; ++i) {
                nr[sa[i]] = nr[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
            }
            r = nr;
        }
        for (auto& e: sa) {
            cout << e + 1 << ' ';
        }
        cout << '\n';
        return sa;
    };

    auto buildLCP = [&](string& s) {
        int N = s.size();
        auto sa = buildSA(s);
        vector<int> isa(N), lcp(N);
        for (int i = 0; i < N; ++i) {
            isa[sa[i]] = i;
        }

        for (int k = 0, i = 0; i < N; ++i) {
            if (isa[i] == 0) continue;
            for (int j = sa[isa[i] - 1]; max(i, j) + k < N && s[i + k] == s[j + k]; ++k);
            lcp[isa[i]] = k ? k-- : 0;

        }
        return lcp;
    };

    auto lcp = buildLCP(s);

    for (int i = 0; i < lcp.size(); ++i) {
        if (i) {
            cout << lcp[i] << ' ';
        } else {
            cout << "x ";
        }
    }
}

문제 링크

https://www.acmicpc.net/problem/3033

풀이 1. Hashing, Rabin-Karp algorithm, Parametric search

• 길이 $l$ 인 부분 문자열이 전체 문자열내에서 두번 이상 등장한다고 하자
• 그 부분 문자열의 부분 문자열들(길이 $1, 2, ..., l$) 또한 전체 문자열내에서 두번 이상 등장한다
• 따라서 결정문제: 길이 $l$ 부분문자열이 2번이상 등장하는가? 에 대한 답의 분포는 이분적이다($T, ..., T, F, F, ..., F$)
• 각 결정문제를 해결할 때에는 라빈카프 알고리즘의 롤링해쉬함수를 이용한다

코드 1.

• 시간복잡도: $O(LlogL)$
  • Parametric search: $O(logL)$
  • 결정문제: $O(L)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int L;
    cin >> L;
    string s;
    cin >> s;

    long long MOD = 1e5 + 3;
    long long MUL = 2;

    auto check = [&](int l) {
        vector<vector<int> > hashTable(MOD);
        long long h = 0;
        long long MUL_POW_L = 1;
        for (int i = 0; i < l; ++i) {
            h *= MUL;
            h += s[i] - 'a' + 1;
            h %= MOD;
            MUL_POW_L *= MUL;
            MUL_POW_L %= MOD;
        }
        hashTable[h].push_back(0);

        for (int i = 1; i + l - 1 < L; ++i) {
            h *= MUL;
            h %= MOD;
            h -= (1LL * (s[i - 1] - 'a' + 1) * MUL_POW_L) % MOD;
            h += s[i + l - 1] - 'a' + 1; 
            h %= MOD;
            if (h < 0) h += MOD;

            for (auto idx: hashTable[h]) {
                if (s.compare(i, l, s, idx, l) == 0) return true;
            }
            hashTable[h].push_back(i);
        }
        return false;
    };

    int lo = 0;
    int hi = L;

    while (lo + 1 < hi) {
        int mid = lo + hi >> 1;
        if (check(mid)) lo = mid;
        else hi = mid;
    }

    cout << lo << '\n';
}

풀이 2. Suffix array and LCP array

• $*max\_element(all(lcp)) = lcp[i]$ 일 때
  • 반복 문자열 최대길이 $= lcp[i]$
  • 반복 문자열 $= s[sa[i]:sa[i] + lcp[i] - 1]$

코드 2.

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int L;
    cin >> L;
    string s;
    cin >> s;

    auto buildSA = [&](string& s) {
        int N = s.size();
        vector<int> sa(N), r(2 * N), nr(2 * N);
        for (int i = 0; i < N; ++i) {
            sa[i] = i;
            r[i] = s[i];
        }
        for (int d = 1; d < N; d <<= 1) {
            auto cmp = [&](int i, int j) {
                return r[i] < r[j] || (r[i] == r[j] && r[i + d] < r[j + d]);
            };
            sort(all(sa), cmp);
            for (int i = 1; i < N; ++i) {
                nr[sa[i]] = nr[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
            }
            r = nr;
        }
        return sa;
    };

    auto buildLCP = [&](string& s) {
        int N = s.size();
        auto sa = buildSA(s);
        vector<int> lcp(N), isa(N);
        for (int i = 0; i < N; ++i) {
            isa[sa[i]] = i;
        }
        for(int k = 0, i = 0;i < N;++i) {
            if(isa[i]){
                for(int j = sa[isa[i]-1]; max(i, j) + k < N && s[i+k] == s[j+k]; ++k);
                lcp[isa[i]] = (k ? k-- : 0);
            }
        }
        return lcp;
    };

    auto lcp = buildLCP(s);
    cout << *max_element(all(lcp)) << '\n';
}