字符串最小表示法 用于求循环同构串中字典序最小的字符串

O(n²)做法

将字符串a[n]扩大二倍 得到b[2 * n]
通过枚举所有起点 得到长度为n的字串 记录字典序最小的字串
就可以得到字符串的最小表示

O(n)做法 例题 : AcWing 137. 雪花雪花雪花 AcWing 158. 项链

设字符串长度为n 
void get_min(int  a[]){
    static int b[2 * n];
    //获得2倍序列
    for(int i = 0 ; i < 2 * n ; i++) b[i] = a[i % n];
    //①设i 为 0 , j 为 1 , k 记录长度
    int i = 0 , j = 1, k; 
    //如果i >= n 或 j >= n 循环结束 否则进行循环
    while(i < n && j < n){
        //向后扫描 
        for(k = 0; k < n && b[i + k] == b[j + k]; k ++);
        //如果k等于n 说明扫描了n个字符仍然相同 说明已经找到了最小表示
        if(k == n) break;
        //如果i+k位置的字符 大于j+k位置的字符 则跳过i后k个字符 
        //因为这时以i ~ i + k为起点的长度为n的字符一定都不是最小表示
        //j同理
        if(b[i + k] > b[j + k]) {
            i += k + 1;
            if(i == j ) i ++;
        }
        else {
            j += k + 1;
            if(i == j) j ++;
        }
    }
    //最终得到 i和j的最小值 就是该字符串最小表示的起点
    k = min(i,j);

    for(int i = 0 ;i < n ; i++) a[i] = b[i + k];
}