神秘科技

求某字符串的所有前缀无限复制后字典序最小的是哪一个前缀。O(n)。

int ans=0;
for(int i=1;i<n;i++){
    if(s[i]>s[i%(ans+1)]) break;
    if(s[i]<s[i%(ans+1)]) ans=i;
}