HDU - 3374 String Problem (최소 표현법 과 최대 표현법)

제목: 이 문자열 이 이동 한 사전 순서 에서 가장 작은 문자열 의 첫 글자 위치 와 사전 순서 에서 가장 큰 문자열 의 첫 글자 위치, 그리고 최소 사전 순서 가 몇 번 나 올 수 있 는 문자열 과 최대 사전 순서 가 몇 번 나 올 수 있 는 문자열 을 물 어 보 는 문자열 입 니 다.
문제 풀이 사고: 몇 번 이 나 올 수 있 는 지 는 순환 절 이 얼마나 되 는 지 봐 야 한다. 나머지 는 최소 표현법 과 최대 표현법 의 누 드 문제 이다.

#include 
#include 
const int N = 1000010;
char str[N];
int len;
int next[N];

void getFail() {
    len = strlen(str);
    int i = 0, j = -1;
    next[0] = -1;
    while (i < len) {
        if (j == -1 || str[i] == str[j]) {
            i++; j++;
            next[i] = j;
        }
        else j = next[j];
    }
}

int getMin() {
    int i = 0, j = 1;
    int l;
    while (i < len && j < len) {
        for (l = 0; l < len; l++)
            if (str[(i + l) % len] != str[(j + l) % len]) break;
        if (l >= len) break;
        if (str[(i + l) % len] > str[(j + l) % len]) i = i + l + 1;
        else j = j + l + 1;
        if (i == j) j++;
    }
    return i < j ? i : j;
}

int getMax() {
    int i = 0, j = 1, k = 0;
    while (i < len && j < len && k < len) {
        int t = str[(i + k) % len] - str[(j + k) % len];
        if (!t) k++;
        else {
            if (t > 0) j = j + k + 1;
            else i = i + k + 1;
            if (i == j) j++;
            k = 0;
        }
    }
    return i < j ? i : j;

}

int main() {
    while (scanf("%s", str) != EOF) {
        getFail();
        int Min = getMin();
        int Max = getMax();
        int c = 0;
        if (len % (len - next[len]) == 0)
            c = len / (len - next[len]);
        else c = 1;
        printf("%d %d %d %d
", Min + 1, c, Max + 1, c);
    }
    return 0;
}