2176: Strange string
Description
给定一个字符串S = {S1, S2, S3 … Sn}, 如果在串SS中, 子串T(|T| = n)为所有长度为n的SS的字串中最小的(字符串的比较), 则称T为”奇怪的字串”. 你的任务就是找出这个字符串.
Input
读入两行, 第一行为n, 第二行为字符串S.
Output
将”奇怪的字串” T输出输入样例
Sample Input
10
asdfasdfas
asdfasdfas
Sample Output
asasdfasdf
HINT
数据范围
对于100%的数据, 保证n≤10000000;
给定的字符串中的字符保证在#33 ~ #254之间.
最小表示法
#include <cstdio>
#include <iostream>
using namespace std;
const int MaxN = 10000010;
int N;
unsigned char s[MaxN];
int MR() {
int i = 0, j = 1, k = 0;
while (i < N && j < N && k < N) {
int t = s[(i + k) % N] - s[(j + k) % N];
if (!t) ++k;
else {
if (t > 0) i += k + 1;
else j += k + 1;
if (i == j) ++j;
k = 0;
}
}
return min(i, j);
}
int main()
{
scanf("%d", &N);
scanf("%s", s);
int k = MR();
for (int i = 0; i < N; ++i)
printf("%c", s[(i + k) % N]);
}
评论 (0)
