whitedeath's Blog

 最小表示法是由IOI2003年冬令营的周源提出来的，今天学习了这后，写下自己的理解和感想~

什么叫最小表示呢，就是把这个字符串看作一个环，在转动的过程中，那个字典序最小的字符串即为字符串的最小表示，具体定义可以参照ZOJ 1729：acm.zju.edu.cn/onlinejudge/showProblem.do

        周源同学介绍的时候是以求两个字符串是否是同构的为中心介绍的，而在求单个字符串的最小表示法上没有细说，个人感觉这个更难以理解一点，因为它相当于自己和自己的下一个表示求是否同构，这个过程中，求出最小表达式，就像kmp算法的next数组，是自己匹配自己的结果~

       这个是网上最一般的最小表示法代码：

int MinimumRepresentation(char *s, int len)
{
    int i = 0, j = 1, count = 0, t;

    while (i < len && j < len && count < len)
    {
        if(s[(i + count) % len] == s[(j + count) % len])
            count++;
        else
        {
            if (s[(i + count) % len] > s[(j + count) % len]) 
                 i = i + count + 1;
            else 
                 j = j + count + 1;
            if (i == j) ++j;
            count = 0;
        }
    }
    return min(i,j);
}

       然而，我在理解这个算法的过程中、和同学讨论的过程中，逐渐发现一些可以改进的地方：

       首先，求余过程很费时间，尤其是字符串比较长的时候。而且本题中最多是len的2倍，所有变求余为作差；

       其次，最后的return min(i,j)可以改成直接return i，因为i <= j是肯定的....因为用通俗的说法，每次i都会把j拉到i+1的位置，所以最后，可以在改变i的时候，将j也拖过去....

      最终代码：

int MinimumRepresentation(char *s, int len)
{
    int i = 0, j = 1, count = 0, t;
    while (i < len && j < len && count < len)
    {
        x = i + count;
        y = j + count;

        if (x >= len) x -= len;          //用减法代替求余 
        if (y >= len) y -= len;          //用减法代替求余

        if (s[x] == s[y])
            count++;
        else
        {
            if (s[x] > s[y])
            {
                i = i + count + 1;
                j = i + 1;         /*将 j 拖至 i + 1 的地方*/
            }
            else
                j = j + count + 1;

            if (i == j) j++;
            count = 0;
        }
    }

    return i;                    //直接return i即可 
}

       思路：这个算法其实就是这样子的，就像刚才说的，是自己跟自己的下一个表示比较，其中i代表本身，j代表这个环的下一个表示方法，然后比较，如果j的表示方法比i小，i就更新了，同时j也更新至i的下一个表示方法，然后继续匹配，直到字符串尾。

 

whitedeath is programmer，我喜欢这个名字，嗯嗯嗯~

以后就在这里贴程序、码感悟、写人生了~~