Favorite Donut

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1378 Accepted Submission(s): 356

Problem Description

Lulu has a sweet tooth. Her favorite food is ring donut. Everyday she buys a ring donut from the same bakery. A ring donut is consists of

Input

First line contain one integer

Output

You should print one line for each test case, consisted of two integers, which represents the starting point (from

Sample Input

abab

aaab

Sample Output

2 0

4 0

Source

2015 ACM/ICPC Asia Regional Changchun Online

题意：Lulu喜欢吃炸面圈，炸面圈有n个部分组成，每个部分由小写字母代表其甜度，Lulu总是从最甜的开始吃，两个方向，哪个最甜吃哪个。输出满足她要求吃法的最开始的下标，和方向。最大最小表示法

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 
  7 using namespace std;
  8 
  9 #define maxn 40008
 10 
 11 int n, Next[maxn];
 12 
 13 void Getnext(char s[], int n)   // kmp获得Next数组，next会出现编译错误，我也不造为什么……
 14 {
 15     int j, k;
 16     j = 0;
 17     k = Next[0] = -1;
 18     while(j < n)
 19     {
 20         if(k == -1 || s[j] == s[k])
 21 
 22          Next[++j] = ++k;
 23         else
 24             k = Next[k];
 25     }
 26 }
 27 
 28 int GETNEXT(char s[], int n)  // 找下标最小的开始的串满足吃法
 29 {
 30     int i, j;
 31     i = 0;
 32     j = 1;
 33     while(i < n && j < n)   // i, j比较，每次让相对字典序小的改变，最后肯定有一个超过n，那个没超过n的就是满足题意的
 34     {
 35         int k = 0;
 36         while( s[i+k] == s[j+k] && k < n)  // 如果这两个下标对应的字典序相等，继续向下比较，知道不等为止
 37             k++;
 38         if(k == n)
 39             break;
 40         if(s[i+k] > s[j+k])
 41         {
 42             if(j+k > i)
 43                 j = j + k + 1;
 44             else
 45                 j = i + 1;
 46         }
 47         else
 48         {
 49             if(i+k > j)
 50                 i = i + k + 1;
 51             else
 52                 i = j + 1;
 53         }
 54     }
 55     return min(i, j);
 56 }
 57 
 58 int KMP(char s[], char s1[], int n, int m)   //在逆串中找开始下标最后边的满足题意的串（就是下标最小的，next， kmp优化
 59 {
 60     int i, j, ans;
 61     i = j = 0;
 62     while(j < m)
 63     {
 64         while( i == -1 || (s[i] == s1[j] && j < m))
 65             i++, j++;
 66 
 67         if(i == n)
 68             ans = j - n;
 69         i = Next[i];
 70     }
 71     return ans;
 72 }
 73 
 74 int main()
 75 {
 76     int c;
 77     scanf("%d", &c);
 78     char s[maxn], s1[maxn], s2[maxn], s3[maxn], s4[maxn];
 79 
 80     while(c--)
 81     {
 82         memset(s, 0, sizeof(s));
 83         memset(s1, 0, sizeof(s1));
 84         memset(s2, 0, sizeof(s2));
 85         memset(s3, 0, sizeof(s3));
 86         memset(s4, 0, sizeof(s4));
 87 
 88         scanf("%d", &n);
 89         scanf("%s", s);
 90         strcpy(s1, s);
 91         strcat(s1, s);
 92 
 93         int a = GETNEXT(s1, n);  // 找到正序的满足题意的下标
 94         strncpy(s3, s1+a, n);   // 把满足题意的s3中
 95 
 96         strrev(s);
 97         strcpy(s2, s);
 98         strcat(s2, s);
 99         int b = GETNEXT(s2, n);  // 找逆串中的满足题意的下标
100         strncpy(s4, s2+b, n);
101 
102         Getnext(s4, n);
103         b = KMP(s4, s2, n, 2*n-1);   // 找逆串中满足题意的最后边的下标，也就是正串中最前边的下标……
104         strncpy(s4, s2+b, n);
105 
106         int g = strcmp(s3, s4);
107 
108         if(g == 0)
109         {
110             if(a+1 <= n-b)
111                 printf("%d 0
", a+1);
112             else
113                 printf("%d 1
", n-b);
114         }
115         else if(g > 0)
116             printf("%d 0
", a+1);
117         else
118             printf("%d 1
", n-b);
119     }
120     return 0;
121 }
122 /*
123 4
124 
125 4
126 aaab
127 4
128 abca
129 6
130 abcabc
131 4
132 abab
133 */

你已经得到最大表示法的下标时，你也可以这么取满足该串的最小下标……

求逆串的最大最小表示法的“最小下标的时候可以用最小循环节做

 1 int solve (char* s){
 2     getNext(s);
 3     if (n % (n - Next[n]))
 4         return n;
 5     else
 6         return n - Next[n];
 7 }
 8 int b=Getmin(s);
 9 int k=solve(s);
10 b = (n - b - 1) % k; // 获得最小的……最小循环节是个神奇的东西……

View Code