题目大意TLDR

有$n$个首尾相接的字符串，每个字符串均由小写字母构成，要求在环上找到一个断点，使得断开后所得的字符串字典序最小。

若有多处断点断开所得的字符串相同，则输出位置最小的断点

Solution

应该就是一个最小表示法的板子题，不多写了

环还是经典的双倍长度处理方法

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#define maxlen 10005
using namespace std;
int n;

int len;

char str[maxlen<<1];
void Work()

{

len=strlen(str);

memcpy(str+len,str,len);

register int i=0,j=1,k=0;

while(i<len && j<len && k<len)

{

if(str[i+k]==str[j+k])

++k;

else if(str[i+k]>str[j+k])

i=i+k+1,k=0;

else if(str[i+k]<str[j+k])

j=j+k+1,k=0;

if(i==j)

++j;

}

printf(“%d\n”,min(i,j)+1);

}
int main()

{

scanf(“%d”,&n);

while(n–)

{

scanf(“%s”,str);

Work();

}

return 0;

}