循环字符串最小表示

题目 From POJ : 

http://poj.org/problem?id=1509

 

#include <iostream>
#include <string>
using namespace std;

int minlist(string &str) {
    if(str.size() < 2) return 0;
    
    str += str;
    
    unsigned int l = 0, h = 1;
    while(h < str.size()) {
        if(str[l] > str[h]) {
            l = h;
            h = l + 1;
        } else if(str[l] < str[h]) {
            h++;
        } else {
            int k = 1;
            while(str[l+k] == str[h+k]) {
                k++;
            }
            if(h+k < str.size()) {
                if(str[l+k] > str[h+k]) {
                    l = h;
                    h = l + 1;
                } else {
                    h ++;
                }
            } else {
                h = str.size();
            }
        }
    }
    
    return l;
}

int main() {
    
    int n;
    cin>>n;
    string str;
    for(int i = 0; i < n; ++i) {
        cin>>str;
        cout<<minlist(str) + 1<<endl;
    }
    
    return 0;
}

 

 

欢迎关注微信公众号——计算机视觉：