最小表示法 学习笔记

模板及讲解

最小表示法是什么

最小表示法就是说我们有一个字符串$S$，然后将其首尾相连之后找到一个$|S|$长的子串使得字典序最小。
这个最小表示法可以用来看两个字符串是否同构，也就是两个字符串是否可以通过环变换互相转换。

解法

对于环的问题，我们可以断环成链，也就是将序列复制一遍放在后面，然后在$[1,n]$范围内为起点$|S|$长的子串都是环上的某种序列。

如果要判断是否同构，可以将一个字符串 Hash，然后再将断环以后的字符串 Hash，在$[1,n]$范围内找起点为$|S|$长的子串，求出Hash值比较即可。

同构也可以用最小表示法来解。也就是说两个不同字符串，如果他们同构，那么他们一定最小表示法一样。

最小表示法求法

O(n^2)

最小表示法有个明显的$O(n^2)$做法，即两个指针$i,j$指向$0,1$，然后枚举判断，如果当前某个值$s_{i+k} > s_{j+k}$，那么$i$不那么优，使$i++$，小于情况类似。等于直接$k++$
这样在极端情况bbbbba下会退化到$O(n^2)$，我们可以尝试优化。

O(n)

我们发现如果存在$s_{i+k} > s_{j+k}$，那么$s[i,i+k]$开头的都不会是最小表示法的开头了。
因为$s[i,i+k]=s[j,j+k]$，所以从$s[i,i+k]$开头的串都会经过这里。
如$i=1,j=4,k=2$时
aacaab
此时$s_{i+k} > s_{j+k}$，即aac 小于 aab
那么$s[i,i+k]$开头的都会遇到c大于b，然后肯定不是答案

所以当出现这种情况时，直接$i+=k$，小于时类似

例题

Bzoj 2882
Lougu

求$|S|$的最小表示法。

代码：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n, a[300000 + 5];

    void clean() {
    }
    int solve() {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        clean();
        int i = 0, j = 1, k = 0;
        while (i < n && j < n && k < n) {
            int t = a[(i + k) % n] - a[(j + k) % n];
            if (!t) ++k; else {
                if (t > 0) i += k + 1; else j += k + 1;
                if (i == j) ++j; // 不要同一个比较
                k = 0; // 记得清零
            }
        }
        int gg = min(i, j);
        for (int i = gg; i <= gg + n - 1; ++i) printf("%d ", a[i % n]);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

写时注意：

1、不要忘了清空$k$
2、不要忘在$i, j$相同时将$j$移动

Bzoj 1398

求$S，T$是否同构。

用最小表示法或者Hash即可。

常见题型