CSES 8. Minimal Rotation (1110)

출처: https://cses.fi/problemset/task/1110

---

문제 설명

A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of acab are acab, caba, abac, and baca.

Your task is to determine the lexicographically minimal rotation of a string.

입력 

The only input line contains a string of length n. Each character is one of a–z.

출력

Print the lexicographically minimal rotation.

입력 예

acab

출력 예

abac

제약조건

1 <= n <=10^6

---

문제 풀이 내용

Booth algorithm (link) 을 구현해서 제일 빠른 문자열이 시작하는 위치를 계산한다.

입력 문자열을 2개 연결하고, 계산한 위치부터 원래 입력받은 문자열 길이만큼 출력한다.

프로그램 내용

/// https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation
/// Booth algorithm

int booth_search(string str)
{
    string str_work = str + str;    /// Concatenate string to it self to avoid modular arithmetic

    int N = str_work.size();

    vector<int> f(N);            ///  Failure function
    f[0] = -1;

    int k = 0;                   /// Least rotation of string found so far

    for(int j=1; j < N; j++)
    {
        char sj = str_work[j];
        int i = f[j-k-1];
        while ( i != -1 && sj != str_work[k+i+1])
        {
            if ( sj < str_work[k+i+1])
                k = j - i - 1;
            i = f[i];
        }
        if (sj != str_work[k+i+1])
        {
            if ( sj < str_work[k])
                k = j;
            f[j-k] = -1;
        }
        else
            f[j-k] = i+1;
    }

    return k;
}

int main() {
...
	int move_size = booth_search(str_in);
	string str_work = str_in + str_in;
	string out = str_work.substr(move_size, str_in.size());
...

 

String Algorithms( link )