Hdu 5442 Favorite Donut (2015 ACM/ICPC Asia Regional Changchun Online 最大最小表示法 + KMP)

题目链接：

　　Hdu 5442 Favorite Donut

题目描述：

　　给出一个文本串，找出顺时针或者逆时针循环旋转后，字典序最大的那个字符串，字典序最大的字符串如果有多个，就输出下标最小的那个，如果顺时针和逆时针的起始下标相同，则输出顺时针。

解题思路：

　　看到题目感觉后缀数组可以搞，正准备犯傻被队友拦下了，听队友解释一番，果断丢锅给队友。赛后试了一下后缀数组果然麻烦的不要不要的(QWQ)，还是最大最小表示法 + KMP来的干净利索。

　　最大表示法：对于一个长度为len文本串，经过循环旋转得到长度为len的新串，新串是所有循环旋转得到的串中字典序最大的。

　　实现方法：对于文本串s，我们可以设定两个指针i, j.

　　　　刚开始的时候i = 0, j = 1;

　　　　当s[i] == s[j]时, (设定指针k) 从i, j 开始比较，直到s[i+k]!= s[j+k]；

　　　　如果s[i+k] < s[j+k], i += k + 1, k = 0;

　　　　　　因为s[i+k] < s[j+k],证明以i开头的串已经没有意义，以i开头的串一定小于以j开头的串的字典序，所以把指针i移动到(i+k+1)的位置继续和以j开头的串比较；

　　　　依此得, j += k + 1, k = 0, 当前j 为最大表示串的起始点；

　　　　最后返回min(i, j)即可。(最小表示法把上面的大于改成小于就ok!)

　　代码实现：

 int Max_Repre (char s[], int n)

 {

     int i = , j = , k = ;

     while (i<n && j<n && k<n)

     {

         int nu = s[(i+k)%n] - s[(j+k)%n];

         if ( !nu )    k++;

         else

         {

             if (nu < )

                 i += k + ;

             else

                 j += k + ;

             if (i == j)

                 j ++;

             k = ;

         }

     }

     return min (i, j);

 }

下面是Hdu 5442 代码，还是要比sa好很多的 (惬意！！！！)

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 int Next[maxn];

 int Max_Repre (char s[], int n)

 {

     int i = , j = , k = ;

     while (i<n && j<n && k<n)

     {

         int nu = s[(i+k)%n] - s[(j+k)%n];

         if ( !nu )    k++;

         else

         {

             if (nu < )

                 i += k + ;

             else

                 j += k + ;

             if (i == j)

                 j ++;

             k = ;

         }

     }

     return min (i, j);

 }

 int Get_Next (char s[], int n)

 {

     int k = -, i = ;

     Next[] = -;

     while (i < n)

     {

         if (k == - || s[k]==s[i])

             Next[++i] = ++k;

         else

             k = Next[k];

     }

     if (n % (n - Next[n]))

         return n;

     return n - Next[n];

 }

 void display (char a[], char s[], int x, int n)

 {

     for (int i=; i<n; i++)

         a[i] = s[(x+i)%n];

     a[n] = ;

 }

 //a大，return true，b大 return false

 bool Judge (int a, int b, char A[], char B[])

 {

     int k = strcmp (A, B);

     if (k == )

         return a<=b ? true:false;

     return k>?true:false;

 }

 int main ()

 {

     int t, n, k, a, b;

     char S[maxn], A[maxn], B[maxn];

     scanf ("%d", &t);

     while (t --)

     {

         scanf ("%d %s", &n, S);

         k = Get_Next (S, n);

         a = Max_Repre (S, n);

         display (A, S, a, n);

         strrev (S);

         b = Max_Repre (S, n);

         display (B, S, b, n);

         b = (n - b - ) % k;

         if (Judge (a, b, A, B))

             printf ("%d 0\n", a + );

         else

             printf ("%d 1\n", b + );

     }

     return ;

 }

巴特西

Hdu 5442 Favorite Donut (2015 ACM/ICPC Asia Regional Changchun Online 最大最小表示法 + KMP)

最新文章

热门文章