Favorite Donut
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 3671 Accepted Submission(s): 919
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 n parts. Every part has its own sugariness that can be expressed by a letter from a to z (from low to high), and a ring donut can be expressed by a string whose i-th character represents the sugariness of the i−th part in clockwise order. Note that z is the sweetest, and two parts are equally sweet if they have the same sugariness.
Once Lulu eats a part of the donut, she must continue to eat its uneaten adjacent part until all parts are eaten. Therefore, she has to eat either clockwise or counter-clockwise after her first bite, and there are 2n ways to eat the ring donut of n parts. For example, Lulu has 6 ways to eat a ring donut abc: abc,bca,cab,acb,bac,cba. Lulu likes eating the sweetest part first, so she actually prefer the way of the greatest lexicographic order. If there are two or more lexicographic maxima, then she will prefer the way whose starting part has the minimum index in clockwise order. If two ways start at the same part, then she will prefer eating the donut in clockwise order. Please compute the way to eat the donut she likes most.
Input
First line contain one integer T,T≤20, which means the number of test case.
For each test case, the first line contains one integer n,n≤20000, which represents how many parts the ring donut has. The next line contains a string consisted of n lowercase alphabets representing the ring donut.
Output
You should print one line for each test case, consisted of two integers, which represents the starting point (from 1 to n) and the direction (0 for clockwise and 1 for counterclockwise).
Sample Input
2
4
abab
4
aaab
Sample Output
2 0
4 0
题目链接：HDU 5442
看到是最近学过的字符串就滚过来写这题了，看了下题意感觉可以做，应该是复制两倍后后缀数组然后瞎搞搞就行了，然而在最后的求逆序位置方向和判断输出上WA了好几发，惨……
题意就是求出给定的可循环字符串的最大字典序排列的位置和方向（逆时针或瞬时间），既然是循环字符串显然要复制一倍放到末尾，然后做一遍$SA$，然后由于字典序最大的时候要起始点最小，因此按排名逆序枚举$sa[i]$数组，当$sa[i] \lt len$或者$sa[i]$使得$lcp(pos, sa[i]) \ge len$就更新答案，如果有排名$sa[i]$使得$lcp(pos, sa[i]) \ge len$时，说明从$sa[i]$和当前答案处开始都可以得到最大字典序，那么当前答案要看情况更新一下，下面的逆序同理也要这样判断更新
然后求逆时针走的最大字典序的最小起始位置，先把串翻转再复制一遍做一次$SA$，然后我们还是按照排名逆序枚举，当然翻转之后我们的枚举位置为$sa[i]$，实际在原串的下标为$len - sa[i] + 1$，因此我们要让$sa[i]$尽量大。
最后从各自开始位置比较两个串的字典序大小，如果都一样，就看起始位置大小，如果起始位置都一样，就按顺时针走
赛后看题解发现用最大表示+$KMP$的做法更简单，顺时针的只要用最大表示法得到的就是最靠左的答案了，逆时针的先把原串翻转一下，得到此时逆时针的最大表示串$max(S’)$（此时下标是最小的，而逆时针下最大的下标才是我们要的），再复制一遍翻转串变成$S’S’$，在$S’S’$里找到最大的匹配起始位置，然后再根据题意映射回原来的下标，再和顺时针的进行比较得出答案，注意比较的时候记得$break$，这里$WA$了一发
后缀数组代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 40050;
int wa[N], wb[N], sa[N], cnt[N], ran[N], height[N], dp[N][17];
char s[N], t[N];
int n;
inline int cmp(int r[], int a, int b, int d)
{
return r[a] == r[b] && r[a + d] == r[b + d];
}
void gethgt(int n)
{
int i, k = 0;
for (i = 1; i <= n; ++i)
ran[sa[i]] = i;
for (i = 0; i < n; ++i)
{
if (k)
--k;
int j = sa[ran[i] - 1];
while (s[j + k] == s[i + k])
++k;
height[ran[i]] = k;
}
}
void RMQinit(int l, int r)
{
for (int i = l; i <= r; ++i)
dp[i][0] = height[i];
for (int j = 1; l + (1 << (j - 1)) - 1 <= r; ++j)
{
for (int i = l; i + (1 << (j - 1)) - 1 <= r; ++i)
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
int ST(int l, int r)
{
int k = 0;
if (l > r)
swap(l, r);
int len = r - l + 1;
while (1 << (k + 1) <= len)
++k;
return min(dp[l][k], dp[r - (1 << k) + 1][k]);
}
int lcp(int l, int r)
{
int rl = ran[l];
int rr = ran[r];
if (rl > rr)
swap(rl, rr);
if (rl == rr)
return n - sa[rl];
return ST(rl + 1, rr);
}
void DA(int n, int m)
{
int i, *x = wa, *y = wb;
for (i = 0; i < m; ++i)
cnt[i] = 0;
for (i = 0; i < n; ++i)
++cnt[x[i] = s[i]];
for (i = 1; i < m; ++i)
cnt[i] += cnt[i - 1];
for (i = n - 1; i >= 0; --i)
sa[--cnt[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1)
{
int p = 0;
for (i = n - k; i < n; ++i)
y[p++] = i;
for (i = 0; i < n; ++i)
if (sa[i] >= k)
y[p++] = sa[i] - k;
for (i = 0; i < m; ++i)
cnt[i] = 0;
for (i = 0; i < n; ++i)
++cnt[x[y[i]]];
for (i = 1; i < m; ++i)
cnt[i] += cnt[i - 1];
for (i = n - 1; i >= 0; --i)
sa[--cnt[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for (i = 1; i < n; ++i)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], k) ? p - 1 : p++;
m = p;
if (m >= n)
break;
}
}
int main(void)
{
int TC, i;
scanf("%d", &TC);
while (TC--)
{
CLR(dp, 0);
scanf("%d%s", &n, s);
for (i = 0; i < n; ++i)
s[i + n] = s[i];
s[n * 2] = '\0';
DA(2 * n + 1, 'z' + 1);
int p = INF, rp = -1;
int c = -1;
for (i = n * 2; i >= 1; --i)
{
if (sa[i] < n)
{
if (p == INF || lcp(p, sa[i]) >= n)
p = min(p, sa[i]);
}
}
strcpy(t, s);
reverse(s, s + 2 * n);
s[n * 2] = '\0';
DA(2 * n + 1, 'z' + 1);
gethgt(2 * n);
RMQinit(1, 2 * n);
for (i = n * 2; i >= 1; --i)
{
if (sa[i] < n)
{
if (rp == -1 || lcp(rp, sa[i]) >= n)
rp = max(rp, sa[i]);
}
}
for (i = 0; i < n; ++i)
{
if (t[(p + i) % n] > s[(rp + i) % n])
{
c = 0;
break;
}
else if (t[(p + i) % n] < s[(rp + i) % n])
{
c = 1;
break;
}
}
rp = n - rp;
++p;
if (c == -1)//字典序一样的情况
{
if (p <= rp)
printf("%d 0\n", p);
else
printf("%d 1\n", rp);
}
else if (c == 0)
printf("%d 0\n", p);
else
printf("%d 1\n", rp);
}
return 0;
}
最大表示+$KMP$代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 40010;
char s[N], t[N], tt[N];
int nxt[N];
void getnext(char s[], int len)
{
int j = 0, k = nxt[0] = -1;
while (j < len)
{
if (k == -1 || s[j] == s[k])
nxt[++j] = ++k;
else
k = nxt[k];
}
}
int kmp(char s[], char t[], int nxt[], int la, int lb)
{
int i = 0, j = 0;
int last = 0;
while (i < la && j < lb)
{
if (j == -1 || s[i] == t[j])
{
++i;
++j;
}
else
j = nxt[j];
if (j == lb)
{
if (i - lb < lb)
last = i - lb;
j = nxt[j];
}
}
return last;
}
int maxPresent(char s[], int len)
{
int i = 0, j = 1, k = 0, t;
while (i < len && j < len && k < len)
{
t = s[(i + k) % len ] - s[(j + k) % len ];
if (!t)
++k;
else
{
if (t < 0)
i += k + 1;
else
j += k + 1;
if (i == j)
++j;
k = 0;
}
}
return min(i, j);
}
int main(void)
{
int TC, len;
scanf("%d", &TC);
while (TC--)
{
scanf("%d%s", &len, s);
int p1 = maxPresent(s, len);
strcpy(t, s);
reverse(t, t + len);
int p2 = maxPresent(t, len);
t[len] = '\0';
strcpy(tt, t);
tt[len] = '\0';
strcat(tt, t);
tt[len << 1] = '\0';
for (int i = 0; i < len; ++i)
t[i] = tt[p2 + i];
t[len] = '\0';
getnext(t, len);
p2 = kmp(tt, t, nxt, len << 1, len);
int big = -1;
for (int i = 0; i < len; ++i)
{
if (s[(p1 + i) % len] > tt[p2 + i])
{
big = 1;
break;
}
else if (s[(p1 + i) % len] < tt[p2 + i])
{
big = 0;
break;
}
}
++p1;
p2 = (len - 1 - p2);
++p2;
if (big == -1)
{
if (p1 <= p2)
printf("%d 0\n", p1);
else
printf("%d 1\n", p2);
}
else
{
if (big == 1)
printf("%d 0\n", p1);
else
printf("%d 1\n", p2);
}
}
return 0;
}