字符串最小表示法模板

第一种

int get_minstring(char s[])
{
    int n =strlen(s);
    int i = 0, j = 1, k;
    while (i < n&&j < n)
    {
        for (k = 0; k < n&&s[(j + k) % n] == s[(i + k) % n]; k++);
        if (k == n)  break;
        if (s[(i + k)%n]>s[(j + k)%n])
        {
            i = i + k + 1;
            if (i == j) i++;
        }
        else
        {
            j = j + k + 1;
            if (i == j) j++;
        }
    }
    return min(i, j);
}

第二种

int get_minstring(char s[])
{
    int n = strlen(s + 1);
    for (int i = 1; i <= n; i++)
        s[n + i] = s[i];
    int i = 1, j = 2,k;
    while (i <= n&&j <= n)
    {
        for ( k = 0; k < n&&s[j + k] == s[i + k]; k++);
        if (k == n)  break;
        if (s[i + k]>s[j + k])
        {
            i = i + k + 1;
            if (i == j) i++;
        }
        else
        {
            j = j + k + 1;
            if (i == j) j++;
        }
    }
    return min(i, j);
}

这两个其实差不多