最小表示法

luckydrawbox · 2022-02-25 12:57:25 · 个人记录

求字符串 S 的字典序最小的表示法。

string zxbsf(string s){
    int n=s.size();
    s+=s;
    int i=0,j=1,k;
    while(i<n&&j<n){
        for(k=0;k<n&&s[i+k]==s[j+k];k++);
        if(!(k^n))
            break;
        if(s[i+k]>s[j+k]){
            i+=k+1;
            if(!(i^j))
                i++;
        }
        else{
            j+=k+1;
            if(!(i^j))
                j++;
        }
    }
    return s.substr(min(i,j),n);
}