链接：https://ac.nowcoder.com/acm/contest/887/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述
A string is perfect if it has the smallest lexicographical ordering among its cyclic rotations.
For example: "0101" is perfect as it is the smallest string among ("0101", "1010", "0101", "1010").

Given a 01 string, you need to split it into the least parts and all parts are perfect.

输入描述:
The first line of the input gives the number of test cases, T (T≤300)T\ (T \leq 300)T (T≤300).  test cases follow.

For each test case, the only line contains one non-empty 01 string. The length of string is not exceed 200.
输出描述:
For each test case, output one string separated by a space.
示例1

输入
复制

4
0
0001
0010
111011110
输出
复制

0
0001
001 0
111 01111 0
题意: 将输入的字符串分最少的次数， 使得每个串都是其循环串中字典序最小的。
思路:可以使用最小表示法， 从后向前， 找到当前字典序最小的循环串位置，注意
找到的串， 仍要继续判断是否为当前最小循环串， 直到满足条件即可以分割。 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string ans[N];
int get_num(string s) // 最小表示法, 返回的为下标
{
	int k = 0, i = 0, j = 1;
	int n = s.size();
	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;
		}
	}
	i = min(i, j);
	return i;
}
int main(){
	int t;
	cin >> t;
	while (t--)
	{
		int cnt = 0;
		string s;
		cin >> s;
		int len = s.size();
		int i = len; // 从后往前的位置
		for (;;)
		{
			if (i <= 0)   // 分完了
				break;
			int wz = get_num(s); 
			string now = s.substr(wz);
			int nwz = 0;
			while (true)   // 直到当前的串最小表示即为0号下标开始
			{
				nwz = get_num(now); // 当前串最小表示的位置
				now = now.substr(nwz);
				if (nwz == 0)  // 为当前最小串
					break;
			}
			ans[++cnt] = now;
			int len1 = now.size();
			i -= len1;
			s = s.substr(0, i);
		}
		for (int i = cnt; i >= 1; i--)
			if (i != 1)
				cout << ans[i] << " ";
			else
				cout << ans[i] << endl;
	}
	return 0;
}