Skip to main content

最小表示法

Summary

最小表示法求字符串所有循环同构中字典序最小者的起始位置。维护两个指针 i、j 与它们的公共前缀长度 k：逐位比较两个起点后移 k 位的字符，相等则 k 加一；一旦某侧字符更大，则以该侧起点开头的后续 k+1 个位置都不可能最优，直接令指针跳过 k+1、重置 k 从头再比。每个位置至多被跳过一次，时间复杂度为 O(n)。实现输出以最小表示起点展开的循环串。

参考资料​

简介​

最小表示法（Minimum String Rotation）用于求字符串 ss 所有循环同构中字典序最小的那个的起始位置。

维护两个指针 i,ji,j（初始为 0,10,1）和公共前缀长度 kk：每次比较 s[(i+k) mod n]s[(i+k)\bmod n] 与 s[(j+k) mod n]s[(j+k)\bmod n]，相同则 kk 加一；若 s[(i+k) mod n]>s[(j+k) mod n]s[(i+k)\bmod n]>s[(j+k)\bmod n]，则以 ii 为起点的后续 k+1k+1 个位置均非最优，直接跳过令 i←i+k+1i\gets i+k+1，同理对称处理 jj。时间复杂度为 O(n)O(n)。

实现​

462 Bcpp
#include <bits/stdc++.h>
using namespace std;

int minimal(string s)
{
	int n=s.size();
	int i=0,j=1,k=0;
	while(k<n&&i<n&&j<n)
	{
		if(s[(i+k)%n]==s[(j+k)%n])
		{
			k++;
		}
		else
		{
			s[(i+k)%n]>s[(j+k)%n]?i=i+k+1:j=j+k+1;
			if(i==j)i++;
			k=0;
		}
	}
	return min(i,j);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s;
	cin>>s;
	int p=minimal(s);
	int n=s.size();
	for(int i=0;i<n;i++)cout<<s[(p+i)%n];
	cout<<'\n';
	return 0;
}

例题​

洛谷 P13270 【模板】最小表示法

若长度为 nn 的字符串 ss 中可以选择一个位置 ii，使得 si⋯sns1⋯si−1‾=t\overline{s_i\cdots s_ns_1\cdots s_{i-1}}=t，则称 ss 与 tt 循环同构。字符串 ss 的 最小表示 为与 ss 循环同构的所有字符串中字典序最小的字符串。

给定一个长度为 nn 的字符串 ss，请求出 ss 的最小表示。

洛谷 P1368 工艺

给定一个长度为 nn 的序列，每次可将最左端元素移到最右端（循环移位）。求所有循环移位中字典序最小的序列。