字符串的最小表示法

一、应用

当题目中出现“环形字符串”等情景时，可以利用字符串的最小表示法来将不同形式的字符串变为一个字符串，这样方便使用Hash等。

二、算法

设字符串为 $S$ 。

• 将 $S$ 复制一份，接到 $S$ 后面，记为 $S'$ .
• 双指针。记两指针分别为 $i,j$ ，比较到了 $i+k,j+k$ 位。（$i,j$ 初始不相同，且一直都不相同）
• 如果 $S'_{i+k} > S'_{j + k}$ ，说明以 $S_i, S_{i+1}, \dotsb , S_{i+k}$ 开头都不可能是最小表示法，$i$ 更新为 $i+k+1$ 。$S'_{i+k} < S'_{j+k}$ 同理。

三、代码

以acwing158为例（模板题）：

#include <cstdio>
#include <cstring>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define MAXN 1000000
char s[(MAXN << 1) + 3], t[(MAXN << 1) + 3];
int l;
int minimize(char *s, int n) {
    int i = 0, j = 1, k;
    while (i <= n && j <= n) {
        for (k = 0; k <= n && s[i + k] == s[j + k]; k++);
        if (k == n) break;
        if (s[i + k] > s[j + k]) {
            i = i + k + 1;
            if (i == j) ++i;
        }
        else {
            j = j + k + 1;
            if (i == j) ++j;
        }
    }
    return min(i, j);
}
int main() {
    scanf("%s%s", s, t), l = strlen(s);
    for (int i = 0; i < l; i++) s[i + l] = s[i];
    for (int i = 0; i < l; i++) t[i + l] = t[i];
    int pos1 = minimize(s, l), pos2 = minimize(t, l);
    bool ok = 1;
    for (int i = 0; i < l; i++)
        if (s[pos1 + i] != t[pos2 + i]) {
            ok = 0;break;
        }
    puts(ok ? "Yes" : "No");
    if (ok)
        for (int i = 0; i < l; i++) putchar(s[pos1 + i]);
    return 0;
}

acwing137:

#include <cstdio>
#include <algorithm>
void swap(int &x, int &y) {
    int t = x;
    x = y, y = t;
}
struct Snowflake {
    int p[15];
} a[100003];
bool cmp(Snowflake x, Snowflake y) {
    for (int i = 1; i <= 6; i++)
        if (x.p[i] < y.p[i])
            return 1;
        else if (x.p[i] > y.p[i])
            return 0;
    return 0;
}
int minimize(Snowflake &a) {
    int i = 1, j = 2, k;
    while (i <= 6 && j <= 6) {
        for (k = 0; k <= 6 && a.p[i + k] == a.p[j + k]; k++);
        if (k == 7) break;
        if (a.p[i + k] > a.p[j + k]) {
            i = i + k + 1;
            //if (i == j) ++i;
        }
        else {
            j = j + k + 1;
            //if (i == j) ++j;
        }
        if (i == j) ++j;
    }
    return std::min(i, j);
}
int n;
int main() {
    Snowflake tmp;
    tmp.p[1] = 5, tmp.p[2] = 6, tmp.p[3] = 1, tmp.p[4] = 2, tmp.p[5] = 3, tmp.p[6] = 4;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        Snowflake tmp1, tmp2;
        int pos1, pos2;
        for (int j = 1; j <= 6; j++)
            scanf("%d", &a[i].p[j]), a[i].p[j + 6] = a[i].p[j];
        pos1 = minimize(a[i]);
        for (int j = 0; j < 6; j++) tmp1.p[j + 1] = a[i].p[pos1 + j];
        for (int j = 1; j <= 3; j++) swap(a[i].p[j], a[i].p[7 - j]);
        for (int j = 1; j <= 6; j++) a[i].p[j + 6] = a[i].p[j];
        pos2 = minimize(a[i]);
        // printf("pos=%d\n", pos2);
        for (int j = 0; j < 6; j++) tmp2.p[j + 1] = a[i].p[pos2 + j];
        // for (int j = 1; j <= 6; j++)
        //     printf("%d ", tmp1.p[j]);
        // puts("");
        // for (int j = 1; j <= 6; j++)
        //     printf("%d ", tmp2.p[j]);
        // puts("");
        if (cmp(tmp1, tmp2))
            for (int j = 1; j <= 6; j++) a[i].p[j] = tmp1.p[j];
        else
            for (int j = 1; j <= 6; j++) a[i].p[j] = tmp2.p[j];
    }
    std::sort(a + 1, a + 1 + n, cmp);
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= 6; j++) printf("%d ", a[i].p[j]);
    //     puts("");
    // }
    for (int i = 2; i <= n; i++) {
        bool equal = 1;
        for (int j = 1; j <= 6; j++)
            if (a[i].p[j] != a[i - 1].p[j]) {equal = 0; break;}
        if (equal)
            return puts("Twin snowflakes found."), 0;
    }
    puts("No two snowflakes are alike.");
    return 0;
}