最小表示法

用途

给一个首尾相连的字符串，找一个位置，从这个位置往后形成一个字符串，使字符串的字典序最小

算法

定义三个指针(i=0),(j=1),(k=0)，(i)和(j)是当前判断的位置，(k)是相同的串的长度，表示(str[i...i+k])和(str[j...j+k])相同。
当(str[i+k]==str[j+k])时，显然，(k++)。
当(str[i+k] > str[j+k])时，发现(i+k)位置的字典序要比(j+k)位置的字典序大，显然，(str[j...j+k])的比(str[i...i+k])的更优，字典序更小，那(i)位置就不能做开头了，必须要往后走，这时(i=i+k+1)。
当(str[i+k] < str[j+k])，(j=j+k+1)。
很显然的是(i)不能等于(j)，所以当(i==j)时，(j(或i)++)
最后(i)和(j)中较小的那一个就是要找的字符串开始的位置

模板

工艺

/*
最小表示法 
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int a[N];
template<class T>inline void read(T &x) {
	x = 0; int f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	x = f ? -x : x;
	return ;
}

int Min() {
	int i = 0, j = 1, k = 0;
	while (i < n && j < n && k < n) {
		if (a[(i + k) % n] == a[(j + k) % n]) k++;              //相等k往后移
		else {
			if (a[(i + k) % n] > a[(j + k) % n]) i += k + 1;    //如上文，i的字典序比j的大
			else j += k + 1;                                    //i的字典序比j的小
			if (i == j) j++;                                    //i不能等于j
			k = 0;                                              //k置0
		}
	}
	return min(i, j);
}

int main() {
	read(n);
	for (int i = 0; i < n; ++i) read(a[i]);
	int ans = Min();
	for (int i = 0; i < n; ++i) printf("%d ", a[(i + ans) % n]);
	return 0;
}

poj1509 Glass Beads

/*
最小表示法 
*/
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int t, n;
char s[N];

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

int main() {
	cin >> t;
	while (t--) {
		memset(s, 0, sizeof(s));
		cin >> s;
		n = strlen(s);
		printf("%d
", Min() + 1);
	}		
	return 0;
}

简单小证明

为什么是(i=i+k+1)呢，我们任取区间([1,k])之间的一个数(k')，因为(str[i+k]>str[j+k])，所以(k')不论取何值，我们发现(str[j+k'...j+k])总是比(str[i+k'...i+k])优，所以(i+k')不能做开头，因为(k')可以取到(k)，所以(i+k)不能做开头，所以(i=i+k+1)。