字符串最小表示.txt

normal template for acm/ICPC

/*
	求字符串的最小表示
	输入：字符串
	返回：字符串最小表示的首字母位置(0...size-1)
*/
template <class T>
int MinString(vector <T> &str)
{
	int i, j, k;
	vector <T> ss(str.size() << 1);
	for (i = 0; i < str.size(); i ++) ss[i] = ss[i + str.size()] = str[i];
	for (i = k = 0, j = 1; k < str.size() && i < str.size() && j < str.size(); ) {
		for (k = 0; k < str.size() && ss[i + k] == ss[j + k]; k ++);
		if (k < str.size()) {
			if (ss[i + k] > ss[j + k])
				i += k + 1;
			else j += k + 1;
			if (i == j) j ++;
		}
	}
	return i < j ? i : j;
}