最小表示法

时间复杂度$O(n)$

每次循环一位将字符串的首个字符放到字符串末尾，然后得到字符串的最小字典序就是最小表示法。(字符串的最小表示)

循环同构[HTML_REMOVED]$s[i..n] + s[1…i-1] = T$ ,那么称T与S循环同构。

最小表示[HTML_REMOVED]与字符串循环同构的最小字典序的字符串

算法核心

是双指针，当$i … i + k - 1$ 这段字符串与$j.. j + k - 1$ 相等，当s[i + k] > s[j + k] 时，那么可以知道从i到i+k这一段开始的字符串是必定不是最小串，因为记为 i + p 为起始位置，那么必定能找到 j + p 为起始位置的字符串字典序更小，那么就需要把i + k + 1，那么如果s[i + k] < s[j + k]这个时候可以知道$j…j+k$这一段必定不满足，需要让j + k + 1 .

那么代码表示

int get_min(char s[]){
    int i = 0 ,j = 1 ;
    while(i < n && j < n){
        int k = 0 ;
        while(k < n && s[i + k] == s[j + k]) k ++ ;  //找到相同的长度
        if(k == n) break ; 
        if(s[i + k] > s[j + k]) i += k + 1 ;  
        else j += k + 1 ;
        if(i == j) j ++ ;    //就是第一个位置就不同
    }
    int k = min(i,j) ; //返回最小的位置
    s[k + n] = 0 ;
    return k ;  //返回最小字符串的起始位置
}

最小表示法