• 最小表示法

最小表示法

最小表示法就是找出字符串S的的循环同构串中字典序最小的一个

std::string findMinimumRepresentation(const std::string& str) {
	int n = str.length();
	int i = 0, j = 1, k = 0;
	while (i < n && j < n && k < n) {
		if (str[(i + k) % n] == str[(j + k) % n]) {
			k++;
		} else {
			if (str[(i + k) % n] > str[(j + k) % n]) {
				i = i + k + 1;
			} else {
				j = j + k + 1;
			}
			if (i == j) {
				j++;
			}
			k = 0;
		}
	}
	int start = std::min(i, j);
	return str.substr(start) + str.substr(0, start);
}