백준9483 Tandem Repeats

작성일 | In

문제 링크

  • http://icpc.me/9483

사용 알고리즘

  • Suffix Array

시간복잡도

  • $O(N \log N)$

풀이

주기가 $p$인 tandem의 개수를 세는 프로시저가 있으면, $p = 1, 2, \cdots, N$에 대해 호출해서 문제를 해결할 수 있습니다.

문자열을 $p$글자씩 분할해서 $B[i]$를 $i$번째 블록이라고 정의합시다. 주기가 $p$인 tandem repeats는 두 가지 형태 중 하나에 해당합니다.

  1. $B[i] = B[i+1]$
    $S$의 LCP 배열에서 RMQ를 하면 블록마다 1번의 RMQ로 확인 가능
  2. $(B[i], B[i+1])$의 최장 공통 접두사 + $(B[i], B[i+1])$의 최장 공통 접미사 $\geq p$
    블록마다 $S$의 LCP 배열과 $S$를 뒤집은 문자열의 $LCP$ 배열에서 각각 1번의 RMQ로 확인 가능

sparse table 등을 이용해 RMQ를 하면 두 가지 경우 모두 각 블록마다 상수 시간에 처리할 수 있으므로 주기가 $p$인 tandem repeats의 개수를 $O(n/p)$ 시간에 구할 수 있습니다.
$\sum N/p = O(N \log N)$이므로 전체 시간 복잡도는 $O(N \log N)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// maximum length, count
pair<int, long long> TandemRepeat(const string &s){
    int n = s.size(), mx = 0; long long cnt = 0;
    string t = s; reverse(t.begin(), t.end());
    auto [sa_s,lcp_s] = SuffixArray(s);
    auto [sa_t,lcp_t] = SuffixArray(t);
    vector<int> pos_s(n), pos_t(n);
    for(int i=0; i<n; i++) pos_s[sa_s[i]] = i;
    for(int i=0; i<n; i++) pos_t[sa_t[i]] = i;

    RMQ<int> rmq_s(lcp_s), rmq_t(lcp_t);
    auto get_s = [&](int a, int b){
        if(a == b) return n - a;
        if(pos_s[a] > pos_s[b]) swap(a, b);
        return rmq_s.query(pos_s[a]+1, pos_s[b]);
    };
    auto get_t = [&](int a, int b){ // reversed string
        a = n - a - 1; b = n - b - 1;
        if(a == b) return n - a;
        if(pos_t[a] > pos_t[b]) swap(a, b);
        return rmq_t.query(pos_t[a]+1, pos_t[b]);
    };

    for(int p=1; p<=n/2; p++){
        for(int i=p; i<n; i+=p){
            int j = min(i+p-1, n-1), fr = get_t(j-p, j), bk = j + 1 < n ? get_s(i, i+p) : 0;
            int st = max(i-fr, i-p), ed = min(j+bk, min(j+p-1,n-1)), len = ed - st + 1;
            if(len >= 2*p) mx = p*2, cnt += len - 2*p + 1;
        }
    }
    return {mx, cnt};
}