2019牛客暑期多校训练营（第七场）A : String
链接：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;
} 
投递美团等公司10个岗位 >
