문제링크

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

 

1605번: 반복 부분문자열

알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열'

www.acmicpc.net

풀이

  • 반복 부분문자열의 길이의 최대는 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());
}

 

728x90

'PS > BOJ' 카테고리의 다른 글

백준 6171번: 땅따먹기  (0) 2022.03.08
백준 3295번: 단방향 링크 네트워크  (0) 2022.03.07
백준 11479번: 서로 다른 부분 문자열의 개수 2  (0) 2022.03.07
백준 3640번: 제독  (0) 2022.03.07
백준 13263번: 나무 자르기  (0) 2022.03.06

문제링크

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

 

11479번: 서로 다른 부분 문자열의 개수 2

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000,000 이하이다.

www.acmicpc.net

풀이

  • 문자열의 서로 다른 부분 문자열 = 모든 접미사의 접두사
  • 각 접미사에 대해 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';
}
728x90

'PS > BOJ' 카테고리의 다른 글

백준 3295번: 단방향 링크 네트워크  (0) 2022.03.07
백준 1605번: 반복 부분문자열  (0) 2022.03.07
백준 3640번: 제독  (0) 2022.03.07
백준 13263번: 나무 자르기  (0) 2022.03.06
백준 4008번: 특공대  (0) 2022.03.06

문제링크

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

 

9248번: Suffix Array

Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들어, 문자열 S=banana의 접미사는 아래와 같이 총 6개가 있다. Suffix i banana 1 anana 2 nana 3 ana 4 na 5 a 6 이를 Suffix 순으로 정

www.acmicpc.net

풀이

  • 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 ";
        }
    }
}
728x90

'PS > BOJ' 카테고리의 다른 글

백준 10266번: 시계 사진들  (0) 2022.02.23
백준 11408번: 열혈강호 5  (0) 2022.02.22
백준 3033번: 가장 긴 문자열  (0) 2022.02.20
백준 2316번: 도시 왕복하기 2  (0) 2022.02.20
백준 13537번: 수열과 쿼리 1  (0) 2022.02.19

문제 링크

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

 

3033번: 가장 긴 문자열

첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다.

www.acmicpc.net

풀이 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';
}
728x90

'PS > BOJ' 카테고리의 다른 글

백준 11408번: 열혈강호 5  (0) 2022.02.22
백준 9248번: Suffix Array  (0) 2022.02.21
백준 2316번: 도시 왕복하기 2  (0) 2022.02.20
백준 13537번: 수열과 쿼리 1  (0) 2022.02.19
백준 1126번: 같은 탑  (0) 2022.02.18

+ Recent posts

티스토리툴바