HDU 4333 Revolving Digits

Posted on

题意

求所有与N循环同构的字符串中，转换成字符串后有几个比它小，相等，比它大 ## 题解 扩展KMP求出extend之后，只需比较下一个字符就可以了，然后输出的是本质不同的字符串的个数 ## 代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>

int T, n;
char s[200000];
int nextx[200000];
int ans1, ans2, ans3;
int cas;

int main()
{
	scanf("%d", &T);
	while (T--)
	{
		scanf("%s", s);
		n = strlen(s);
		nextx[0] = n;
		int pos = -1, last = -1;
		for (int i = 1; i < n; i++)
		{
			int k = (pos == -1 || i > last) ? 0 : std::min(nextx[i - pos], last - i + 1);
			while (k < n && s[k] == s[(i + k) % n])
			{
				k++;
			}
			nextx[i] = k;
			if (i + nextx[i] - 1 > last)
			{
				pos = i;
				last = i + nextx[i] - 1;
			}
		}
		ans1 = ans2 = ans3 = 0;
		for (int i = 0; i < n; i++)
		{
			if (nextx[i] == n)
			{
				ans2++;
			}
			else
			{
				if (s[(i + nextx[i]) % n] > s[nextx[i]])
				{
					ans3++;
				}
				else
				{
					ans1++;
				}
			}
		}
		cas++;
		printf("Case %d: %d %d %d\n", cas, ans1 / ans2, ans2 / ans2, ans3 / ans2);
	}
	return 0;
}