[Codeforces] suffix array

 

https://codeforces.com/edu/course/2/lesson/2/1

Courses - Codeforces

[문제] 

S = ababba

SUFFIX ARRAY = { ", a, ba, bba, abba, babba, ababba}

를 정렬하면

{", a, abba, ababba, bba, babba}

How to store all these suffixes?  

What about string array? It will be too much b.c. the total length of the array is n^2

Instead let's store only the index of the first letter of each suffix 

위의 예) {6, 5, 2, 0, 3, 1} 

따라서, 이렇게 정렬된 suffix array의 첫번째 글자의 인덱스를 가지는 배열을 만드는 알고리즘을 알려주고 있습니다.

 

[방법] 

 Append $ at each sufiix and  make all strings get the same length

 

6	$ababba
5	a$ababb
0	ababba$
2	abba$ab
4	ba$abab
1	babba$a
3	bba$aba

 When we compare to strings , we go from left to right and don't go further after the $ (b.c. $ is less than any other character)

더 cyclic 하게 S를 이어 붙여서 모든 string의 길이를 2의 제곱수로 만듭니다.

1 -> 2 -> 4 -> 8.. 이렇게 iteration을 돌며 정렬하기 위함입니다.

 

iteration k :

sorted strings S[i...i + 2 ^ k - 1]

Transition k to k+1

이후는 생략..

 

https://codeforces.com/edu/course/2/lesson/2/1/practice/contest/269100/problem/A

Courses - Codeforces

[코드] 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    string s;
    cin>>s;
    s += "$";
    int n = s.size();
    vector<int> p(n), c(n);
    {
        // k = 0
        vector<pair<char,int>> a(n);
        for(int i= 0; i < n; i++) a[i] = {s[i], i};
        sort(a.begin(),a.end());
        
        for(int i = 0 ; i < n; i++) p[i] = a[i].second;
        c[p[0]]=0;
        for(int i = 1; i < n; i++){
            if(a[i].first == a[i-1].first){
                c[p[i]] = c[p[i-1]];
            }
            else {
                c[p[i]] = c[p[i-1]] + 1;
            }
        }
    }
    
    int k = 0 ; 
    while((1<<k) < n){
        // k - > k + i-1
        vector<pair<pair<int,int>,int>> a(n); //left,right,index
        for(int i = 0 ; i < n; i++){
            a[i] = {{c[i], c[(i + (1 << k)) % n]},i};
        }
        sort(a.begin(),a.end());
        for(int i = 0; i<n; i++) p[i] = a[i].second;
        c[p[0]] = 0;
        for(int i = 1; i < n; i++){
            if(a[i].first == a[i-1].first){
                c[p[i]] = c[p[i-1]];
            }
            else {
                c[p[i]] = c[p[i-1]] + 1;
            }
        }
        k++;
    }
    for(int i = 0 ; i < n; i++){
        cout<<p[i]<<" ";
    }
    return 0;
}