最小最大表示法，求环形字符串的最小最大字典树（模板）

最小表示法：

   初始时，i=0,j=1，分别以i，j，为起始点顺着i，j，往下比较直到找的str[i+k]!=str[j+k]，然后分两种情况考虑：

1、  str[i+k]>str[j+k]，i变成i=i+k+1，j不变，然后继续往下比较。

2、  str[i+k]<str[j+k]，j变成j=j+k+1，i不变，然后继续往下比较。

直到i或j大于串长，找较小者。

 

int work(int m)
{
    int i,j,l;
    i=0; j=1;
    while(i<m && j<m)
    {
        for(l=0;l<m;l++) 
            if(str[(i+l)%m]!=str[(j+l)%m]) break;
        if(l>m) break;
        if(str[(i+l)%m] > str[(j+l)%m])
            i=i+l+1;
        else
            j=j+l+1;
        if(i==j) j=i+1;
    }
    if(i<j) return i;
    return j;
}

 最大表示法，返回最大字典序：

int work(int len,char pat[])  //最大表示法
{
   //int len = strlen(pat);
   int i=0,j=1,k=0;
   while(i<len && j<len && k<len)
   {
       int t = pat[(i+k)%len] - pat[(j+k)%len];
       if(!t) k++;
       else
       {
           if(t>0) j = j+k+1;
           else i = i+k+1;
           if(i == j) j++;
           k = 0 ;
       }
   }
   return i<j?i:j;
}