字符串——最小表示法

定义

在字符串 \(S\) 的所有，与其循环同构的字符串 \(T\) 中，字典序最小的一个。

循环同构：字符串 \(S\) 循环移位，所有可以得到的字符串 \(T\) 与 \(S\) 循环同构。

暴力

枚举与 \(S\) 循环同构的每一个字符串，比较其字典序。

枚举复杂度 \(\mathcal O(n)\)，字典序比较复杂度 \(\mathcal O(n)\)，整体复杂度 \(\mathcal O(n^2)\)。

优化

可以先将字符串拼接一倍，注意到最小表示一定是以一个 \(k\) 开头的长度为 \(n\) 的字串。

于是，可以用两个指针，分别表示两个比较优化的解，然后考虑扩展。

对于当前的，如果相同，那么扩展长度；如果不同，那么长度清零，然后考虑移动指针。

对于大的，考虑移动，指针向后移动一位，进行下一轮判断。

借用 OI-Wiki 的代码，

k, i, j = 0, 0, 1
while k < n and i < n and j < n:
    if sec[(i + k) % n] == sec[(j + k) % n]:
        k += 1
    else:
        if sec[(i + k) % n] > sec[(j + k) % n]:
            i += 1
        else:
            j += 1
        k = 0
        if i == j:
            i += 1
i = min(i, j)

时间复杂度 \(\mathcal O(n^2)\)，对于随机数据还可以。

最小表示法

考虑继续优化，注意到如果找到了一组不同的，那么大的可以直接移动下去。

因为对于前面的每一个字串，这一个大的每一个字串都可以唯一的对应一个更优的字符串。

代码依旧借用 OI-Wiki 的：

k, i, j = 0, 0, 1
while k < n and i < n and j < n:
    if sec[(i + k) % n] == sec[(j + k) % n]:
        k += 1
    else:
        if sec[(i + k) % n] > sec[(j + k) % n]:
            i = i + k + 1
        else:
            j = j + k + 1
        if i == j:
            i += 1
        k = 0
i = min(i, j)

然后贴一下我的代码：

template<typename tp>
basic_string<tp> mcs(basic_string<tp> a) {
	int n = a.size(); a = a + a;
	int i = 0, j = 1;
	for (int k = 0; k < n && i < n && j < n; ) {
		const auto ii = a[i + k], jj = a[j + k];
		if (ii == jj) continue(++k);
		else if (ii > jj) i = i + k + 1;
		else j = j + k + 1;
		k = 0; if (i == j) ++j;
	}
	return a.substr(min(i, j), n);
}