3033번: DVAPUT

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

Rabin-Karp 알고리즘으로 $O(l)$에 길이가 x인 같은 문자열이 두 번 나오는지 확인할 수 있다.
x에 대해 파라메트릭 서치를 한다.

시간복잡도는 $O(l\lg l)$

#include<cstdio>
#include<cstring>
#include<unordered_set>
using namespace std;
const long long mod = (1LL << 55) - 55;
int l;
char s[200001];
int main() {
    scanf("%d%s", &l, s);
    int low = 1, up = l, mid;
    while (low <= up) {
        mid = low + up >> 1;
        unordered_set<long long> st;
        long long p = mod - 1, t = 0;
        int i = 0;
        for (; i < mid; i++) t = (t * 127 + s[i]) % mod, p = p * 127 % mod;
        for (; i <= l; i++) {
            if (st.find(t) != st.end()) break;
            st.insert(t);
            t = (t * 127 + p*s[i - mid] + s[i]) % mod;
        }
        i > l ? up = mid - 1 : low = mid + 1;
    }
    printf("%d", up);
    return 0;
}

답은 lcp 길이의 최댓값이다.

시간복잡도는 $O(l\lg l)$

#include<cstdio>
#include<algorithm>
using namespace std;
int l, c[200000], a[200000], b[200000], sa[200000], sz, r;
char s[200001];
void csort() {
    for (int i = 0; i < sz; i++) c[i] = 0;
    for (int i = 0; i < l; i++) c[a[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i - 1];
    for (int i = l; i--;) sa[--c[a[b[i]]]] = b[i];
}
int main() {
    scanf("%d%s", &l, s);
    sz = max(l, 128);
    for (int i = 0; i < l; i++) a[i] = s[i], b[i] = i;
    csort();
    for (int i = 1, k; i <= l; i <<= 1) {
        k = 0;
        for (int j = l - i; j < l; j++) b[k++] = j;
        for (int j = 0; j < l; j++) if (sa[j] >= i) b[k++] = sa[j] - i;
        csort();
        k = 0;
        for (int j = 0; j < l; j++) b[sa[j]] = !j || sa[j - 1] + i < l && sa[j] + i < l && a[sa[j - 1]] == a[sa[j]] && a[sa[j - 1] + i] == a[sa[j] + i] ? k : ++k;
        for (int j = 0; j < l; j++) a[j] = b[j];
    }
    for (int i = 0, j = 0; i < l; r = max(r, j ? j-- : 0), i++)
        while (a[i] && s[i + j] == s[sa[a[i] - 1] + j]) j++;
    printf("%d", r);
    return 0;
}

9248번: Suffix Array

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

suffix array와 LCP를 구하는 문제

시간복잡도는 $O(l\lg l)$

#include<cstdio>
#include<cstring>
int n, sz, a[500000], b[500000], sa[500000], c[500000], lcp[500000];
char s[500001];
void csort() {
    for (int i = 0; i < sz; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[a[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i - 1];
    for (int i = n; i--;) sa[--c[a[b[i]]]] = b[i];
}
void SA() {
    sz = n > 128 ? n : 128;
    for (int i = 0; i < n; i++) a[i] = s[i], b[i] = i;
    csort();
    for (int i = 1, k; i <= n; i <<= 1) {
        k = 0;
        for (int j = n - i; j < n; j++) b[k++] = j;
        for (int j = 0; j < n; j++) if (sa[j] >= i) b[k++] = sa[j] - i;
        csort();
        k = 0;
        for (int j = 0; j < n; j++) b[sa[j]] = !j || sa[j] + i < n && sa[j - 1] + i < n&&a[sa[j]] == a[sa[j - 1]] && a[sa[j] + i] == a[sa[j - 1] + i] ? k : ++k;
        for (int j = 0; j < n; j++) a[j] = b[j];
    }
}
void LCP() {
    for (int i = 0, j = 0; i < n; lcp[a[i++]] = j ? j-- : 0)
        while (a[i] && s[i + j] == s[sa[a[i] - 1] + j]) j++;
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    SA();
    LCP();
    for (int i = 0; i < n; i++) printf("%d ", sa[i] + 1);
    printf("\nx");
    for (int i = 1; i < n; i++) printf(" %d", lcp[i]);
    return 0;
}

13264번: 접미사 배열 2

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

앞에서부터 1, 2, 4, ...개를 보며 계수 정렬하는 풀이
http://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm/

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<cstring>
char s[100001];
int r[100000], t[100000], sa[100000], c[100000], n, sz;
void csort() {
    for (int i = 0; i < sz; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[r[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i - 1];
    for (int i = n; i--;) sa[--c[r[t[i]]]] = t[i];
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    sz = 128 < n ? n : 128;
    for (int i = 0; i < n; i++) r[i] = s[i], t[i] = i;
    csort();
    for (int i = 1, k; i < n; i <<= 1) {
        k = 0;
        for (int j = n - i; j < n; j++) t[k++] = j;
        for (int j = 0; j < n; j++) if (sa[j] >= i) t[k++] = sa[j] - i;
        csort();
        k = 0;
        for (int j = 0; j < n; j++) t[sa[j]] = !j || sa[j] + i < n && sa[j - 1] + i < n &&r[sa[j]] == r[sa[j - 1]] && r[sa[j] + i] == r[sa[j - 1] + i] ? k : ++k;
        for (int j = 0; j < n; j++) r[j] = t[j];
    }
    for (int i = 0; i < n; i++) printf("%d\n", sa[i]);
    return 0;
}

13013번: 접미사 배열 2

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


$O(n)$

입력으로 주어진 접미사 배열: a[0...n-1]
구하고자 하는 문자열: s[0...n-1]
아래에서 문자 혹은 문자열간 크기 비교시 작다는 것은 사전순으로 빠름을 의미함.

다음 성질들을 만족한다.
1. 임의의 i, j에 대해 s[a[i]...n-1] < s[a[j]...n-1] <-> 임의의 i에 대해 s[a[i]...n-1] < s[a[i+1]...n-1]
2. 임의의 i에 대해 s[a[i]] <= s[a[i+1]]

따라서 s[a[i]] < s[a[i+1]]를 만족하는 i의 개수가 가능한 작아야 하며,  이 값+1이 답이다.

s[a[i]] < s[a[i+1]]를 무조건 만족해야하는 경우는 그 다음 문자들로 구성된 문자열간의 관계가 s[a[i]+1...n-1] > s[a[i+1]+1...n-1]인 경우이다.(빈 문자열은 사전순으로 가장 빠르다고 가정)
또한 이 문자열간 크기 관계는 주어진 접미사 배열로 확인할 수 있다.

#include<cstdio>
int a[50], b[51], n, r = 1;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i), b[a[i]] = i + 1;
    for (int i = 1; i < n; i++) r += b[a[i - 1] + 1] > b[a[i] + 1];
    printf("%d", r);
    return 0;
}