A38890. 最小下标小蓝有一个由大写字母ABCDEF组成的字符串S，长度为n，字符串的下标依次为0到n-1。小蓝按照如下方法生成一个无限长的字符串：首先选定一个0到n-1之间的数，作为初始下标。从初始下标开始，将下标对应的字符加入到字符串的结尾，将字符的序号（A到F依次对应1到6）与下标相加作为新的下标值，如果下标大于等于n，将其对n求余。重复此过程，即得到无限长的字符串。例如，对于字符串ACDF，当初始下…
填空题
困难
知识点
题目描述
最小下标
小蓝有一个由大写字母ABCDEF组成的字符串S，长度为n，字符串的下标依次为0到n-1。
小蓝按照如下方法生成一个无限长的字符串：
首先选定一个0到n-1之间的数，作为初始下标。
从初始下标开始，将下标对应的字符加入到字符串的结尾，将字符的序号（A到F依次对应1到6）与下标相加作为新的下标值，如果下标大于等于n，将其对n求余。重复此过程，即得到无限长的字符串。例如，对于字符串ACDF，当初始下标是0时，生成的字符串为：ACACACACAC...
再如，对于字符串DCBA，当初始下标是1时，生成的字符串为：CDDDDDDDDD.…
给定小蓝的字符串S，请问当初始下标为多少时，生成的字符串最小。
输入格式
输入一行包含一个字符串。
输出格式
输出一行，包含一个整数，为所求的下标，如果有多个下标满足要求，输出最小的那个。
样例输入1
DCBA
样例输出1
3
样例输入2
AAAA
样例输出2
0
评测用例规模与约定
令|S|表示S的长度。
对于30%的评测用例，1<=|S|<=100。
对于50%的评测用例，1<=|S|<=1000。
对于70%的评测用例，1<=|S|<=10000。
对于80%的评测用例，1<=|S|<=100000。
对于所有评测用例，1<=|S|<=1000000。
参考答案
s = input()
l = len(s) # 字符串的长度
def getNext(i): # 计算出下标为i的下一个下标
return (i + ord(s[i]) - ord('A') + 1)%l
ans = 0
min_s = 'Z'*l # 初始化最小字符串为最大
for i in range(l): #i为s的下标
c = s[i] # 取出该位上的字符 作为c字符串的首字母
t = i # 储存下标位
while len(c) < l: # 字符串c长度大于等于l时停止循环
j = getNext(t) # 计算出下一位下标
c += s[j] # 连接下一位字符
t = j # 更新当下坐标位
if c > min_s:
break
if c < min_s: # 更新字典序最小的字符串
min_s = c
ans = i # 更新c字符串第一个字符的初始位
print(ans)
上一题
下一题