跃迁引擎启动

字符串最小表示法

发表于 更新于 分类于 阅读次数：

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int getmin(char* s){
    int n = strlen(s), i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n){
        int t = s[(i + k) % n] - s[(j + k) % n];
        if (!t) k++;
        else {
            if (t > 0) i += k + 1;
            else j += k + 1;
            if (i == j) j++;
            k = 0;
        }
    }
    return min(i, j) + 1;
}