字符串的最小表示法

最小表示法

---

最小表示法有很多含义，比如有集合最小表示法，字符串最小表示法等.

这里介绍的是字符串的最小表示法.

仍给一个字符串，例如ababc.

可以通过循环一位的方式构造出来 $n$ 个字符串，循环一位是指将第一个字符移动到字符串的末尾，即：

1. 循环 $1$ 位，得babca；
2. 循环 $2$ 位，得abcab；
3. 循环 $3$ 位，得bcaba；
4. 循环 $4$ 位，得cabab；

其中字典序最小的字符串，就被称为这个字符串的最小表示法.

• 暴力去解决这个问题，时间复杂度为 $O(n^2)$.

需要先把 $n$ 个字符串都构造出来，这就是 $O(n^2)$ 的时间复杂度，还需要再从前往后遍历一遍，找到字典序最小的字符串.

• 而最小表示法有一个算法，可以把时间复杂度降到 $O(n)$.

  • 可以发现，每次循环都是把第一个字符移动到字符串的末尾，所以可以考虑使用破环成链的方法，即把这 $n$ 个字符串，对应到一条链上.

  即将字符串复制一遍，放到本身的末尾，这样字符串的长度就扩大了一倍，为 $2n$.

  例如ababc可以扩大为ababcababc.

  此时，第一个字符串对应的区间就是 $[1,n]$；

  第二个字符串对应的区间就是 $[2,n+1]$；

  第 $x$ 个字符串对应的区间就是 $[x,n+x-1]$；

  值得注意的是，原串会在此字符串中对应两个区间，即 $[1,n]$ 和 $[n+1,2n]$.

  为了防止字符串不能一一对应，所以将最后一个字符去掉，最终字符串的长度即为 $2n-1$.

  即ababc最终扩大为ababcabab.

• 如果去找字典序最小的字符串呢？

  • 这里使用的是双指针算法.
  • 第一个指针 $i$ 从第一个位置开始走，第二个指针 $j$ 从第二个位置开始走；
  • 第一个指针 $i$ 代表从 $i$ 这个位置开始的长度为 $n$ 的字符串；第二个指针 $j$ 代表从 $j$ 这个位置开始的长度为 $n$ 的字符串；
  • 两个指针分别往后走，直接暴力比较 $i$ 和 $j$ 所代表的字符串的大小关系；

  设 $s$ 为扩展后的字符串.

  即先比较 $s_i$ 和 $s_j$，如果相同再比较 $s_{i+1}$ 和 $s_{j+1}$，以此类推，直到找到第一个不同的字母为止，设此时为 $s_{i+k}$ 和 $s_{j+k}$；

  不妨设 $s_{i+k}>s_{j+k}$，则说明以 $i$ 这个位置开始的长度为 $n$ 的字符串，一定不是最小表示法，因此可以说明 $i$ 是不符合要求的.

  进一步可以发现，以 $[i,i+k]$ 这一段中任何一个位置开始的长度为 $n$ 的字符串，也一定不是最小表示法.

  证明

  设 $i’\in [i,i+k]$，则以 $i’$ 这个位置开始的长度为 $n$ 的字符串一定不是最小表示法.

  显然，可以找到对应的 $j’\in [j,j+k]$，可以发现以 $j’$ 这个位置开始的长度为 $n$ 的字符串的字典序一定比 $i’$ 的要小.

  证毕

  所以 $i$ 就可以直接从 $i+k+1$ 再开始枚举.

  同理，若 $s_{i+k}<s_{j+k}$，则 $j$ 就可以直接从 $j+k+1$ 再开始枚举.

  可以发现，$i$ 和 $j$ 每次都会往后走，最多各自执行 $n$ 次，所以时间复杂度为 $O(n)$.

  在实现时，需要注意 $k<n$，因为字符串的长度是 $n$.

  特殊地，如果循环结束时，没有发现有任何一个位置不同，则说明两段字符串完全相同，这时直接退出双指针算法即可.

  因为如果出现这种情况，说明原串一定是一个循环串，且 $i$ 和 $j$ 之间的部分，一定是第一个循环节，此时两个指针已经都已经经过了循环节可能出现的所有起点，所以此时就已经遍历过了所有不同的字符串了.

  
  

  循环节图示

AcWing 158. 项链

原题链接

有一天，达达捡了一条价值连城的宝石项链，但是，一个严重的问题是，他并不知道项链的主人是谁！

在得知此事后，很多人向达达发来了很多邮件，都说项链是自己的，要求他归还（显然其中最多只有一个人说了真话）。

达达要求每个人都写了一段关于自己项链的描述： 项链上的宝石用数字 $0$ 至 $9$ 来标示。

一个对于项链的表示就是从项链的某个宝石开始，顺指针绕一圈，沿途记下经过的宝石，比如项链： $0-1-2-3$，它的可能的四种表示是 $0123$、$1230$、$2301$、$3012$。

达达现在心急如焚，于是他找到了你，希望你能够编写一个程序，判断两个给定的描述是否代表同一个项链（注意，项链是不会翻转的）。

也就是说给定两个项链的表示，判断他们是否可能是一条项链。

输入格式

输入文件只有两行，每行一个由字符 $0$ 至 $9$ 构成的字符串，描述一个项链的表示（保证项链的长度是相等的）。

输出格式

如果两个对项链的描述不可能代表同一个项链，那么输出 No，否则的话，第一行输出一个 Yes，第二行输出该项链的字典序最小的表示。

数据范围

设项链的长度为 $L$，$1\le L\le 1000000$

输入样例：

2234342423
2423223434
1
2

输出样例：

Yes
2234342423
1
2

时/空限制： 1s / 128MB
来源： 《算法竞赛进阶指南》
算法标签：字符串 最小表示法

yxc’s Solution

给出两个字符串，若它们的最小表示法不相等，输出No，否则输出Yes并输出它们的最小表示法.

#include 
#include 
#include 

using namespace std;

const int N = 2000010;

int n;
char a[N],b[N];

int get_min(char s[]) {
	int i = 0, j = 1;
	while(i < n && j < n){
		int k = 0;
		while (k < n && s[i + k] == s[j + k]) k ++ ;
		if (k == n ) break;
		if(s[i + k] > s[j + k]) i += k + 1;
		else j += k+1;
		if(i == j) j ++ ;
	}
	int k = min(i, j);
	s[k + n] = 0;
	return k;
}

int main() {
	scanf("%s%s", a, b);
	n = strlen(a);
	memcpy(a + n, a, n); // 将从 a 开始，长度为 n 的这一段复制到 a+n 开始的地方
	memcpy(b + n, b, n);
	
	int x = get_min(a), y = get_min(b);
	if(strcmp(a + x,b + y)) puts("No"); // 最小表示法会将字符串终止的位置赋成 '\0'
	else {
		puts("Yes");
		puts(a + x);
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41