SPOJ REPEATS Repeats

103 阅读 0 评论 68 点赞

我是靠谱客的博主漂亮灯泡，这篇文章主要介绍SPOJ REPEATS Repeats，现在分享给大家，希望可以做个参考。

Description

A string s is called an (k,l)-repeat if s is obtained by concatenating k>=1 times some seed string t with length l>=1. For example, the string

s = abaabaabaaba

is a (4,3)-repeat with t = aba as its seed string. That is, the seed string t is 3 characters long, and the whole string s is obtained by repeating t 4 times.

Write a program for the following task: Your program is given a long string u consisting of characters ‘a’ and/or ‘b’ as input. Your program must find some (k,l)-repeat that occurs as substring within u with k as large as possible. For example, the input string

u = babbabaabaabaabab

contains the underlined (4,3)-repeat s starting at position 5. Since u contains no other contiguous substring with more than 4 repeats, your program must output the maximum k.

Input

In the first line of the input contains H- the number of test cases (H <= 20). H test cases follow. First line of each test cases is n - length of the input string (n <= 50000), The next n lines contain the input string, one character (either ‘a’ or ‘b’) per line, in order.

Output

For each test cases, you should write exactly one interger k in a line - the repeat count that is maximized.

Example

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Input:
1
17
b
a
b
b
a
b
a
a
b
a
a
b
a
a
b
a
b

Output:
4

since a (4, 3)-repeat is found starting at the 5th character of the input string.

求子串中重复次数最多是多少，后缀数组枚举长度。

复制代码

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define fi first
#define se second
#define mp(i,j) make_pair(i,j)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int read()
{
	char ch = getchar();
	while (ch<'0' || ch>'9') ch = getchar();
	int x = ch - '0';
	while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0';
	return x;
}
int T = 0;

struct Sa
{
	char s[N];
	int rk[2][N], sa[N], h[N], w[N], now, n;
	int rmq[N][20], lg[N];

bool GetS()
	{
		scanf("%d", &n);
		rep(i, 1, n) scanf("%s", s + i);
		return true;
	}

void getsa(int z, int &m)
	{
		int x = now, y = now ^= 1;
		rep(i, 1, z) rk[y][i] = n - i + 1;
		for (int i = 1, j = z; i <= n; i++)
			if (sa[i] > z) rk[y][++j] = sa[i] - z;

rep(i, 1, m) w[i] = 0;
		rep(i, 1, n) w[rk[x][rk[y][i]]]++;
		rep(i, 1, m) w[i] += w[i - 1];
		per(i, n, 1) sa[w[rk[x][rk[y][i]]]--] = rk[y][i];
		for (int i = m = 1; i <= n; i++)
		{
			int *a = rk[x] + sa[i], *b = rk[x] + sa[i - 1];
			rk[y][sa[i]] = *a == *b&&*(a + z) == *(b + z) ? m - 1 : m++;
		}
	}

void getsa(int m)
	{
		//n = strlen(s + 1);
		rk[1][0] = now = sa[0] = s[0] = 0;
		rep(i, 1, m) w[i] = 0;
		rep(i, 1, n) w[s[i]]++;
		rep(i, 1, m) rk[1][i] = rk[1][i - 1] + (bool)w[i];
		rep(i, 1, m) w[i] += w[i - 1];
		rep(i, 1, n) rk[0][i] = rk[1][s[i]];
		rep(i, 1, n) sa[w[s[i]]--] = i;

rk[1][n + 1] = rk[0][n + 1] = 0;	//多组的时候容易出bug
		for (int x = 1, y = rk[1][m]; x <= n && y <= n; x <<= 1) getsa(x, y);
		for (int i = 1, j = 0; i <= n; h[rk[now][i++]] = j ? j-- : j)
		{
			if (rk[now][i] == 1) continue;
			int k = n - max(sa[rk[now][i] - 1], i);
			while (j <= k && s[sa[rk[now][i] - 1] + j] == s[i + j]) ++j;
		}
	}

void getrmq()
	{
		h[n + 1] = h[1] = lg[1] = 0;
		rep(i, 2, n) rmq[i][0] = h[i], lg[i] = lg[i >> 1] + 1;
		for (int i = 1; (1 << i) <= n; i++)
		{
			rep(j, 2, n)
			{
				if (j + (1 << i) > n + 1) break;
				rmq[j][i] = min(rmq[j][i - 1], rmq[j + (1 << i - 1)][i - 1]);
			}
		}
	}

int lcp(int x, int y)
	{
		int l = min(rk[now][x], rk[now][y]) + 1, r = max(rk[now][x], rk[now][y]);
		return min(rmq[l][lg[r - l + 1]], rmq[r - (1 << lg[r - l + 1]) + 1][lg[r - l + 1]]);
	}

void work()
	{
		GetS();	getsa(300);	getrmq();
		int ans = 1;
		rep(L, 1, n)
		{
			for (int i = 1; i + L <= n; i += L)
			{
				int R = lcp(i, i + L);
				ans = max(ans, R / L + 1);
				if (i >= L - R % L)
				{
					ans = max(lcp(i - L + R%L, i + R%L) / L + 1, ans);
				}
			}
		}
		printf("%dn", ans);
	}
}sa;

int main()
{
	T = read();
	while (T--) sa.work();
	return 0;
}

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
#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define fi first
#define se second
#define mp(i,j) make_pair(i,j)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int read()
{
	char ch = getchar();
	while (ch<'0' || ch>'9') ch = getchar();
	int x = ch - '0';
	while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0';
	return x;
}
int T = 0;

struct Sa
{
	char s[N];
	int rk[2][N], sa[N], h[N], w[N], now, n;
	int rmq[N][20], lg[N];

	bool GetS()
	{
		scanf("%d", &n);
		rep(i, 1, n) scanf("%s", s + i);
		return true;
	}

	void getsa(int z, int &m)
	{
		int x = now, y = now ^= 1;
		rep(i, 1, z) rk[y][i] = n - i + 1;
		for (int i = 1, j = z; i <= n; i++)
			if (sa[i] > z) rk[y][++j] = sa[i] - z;

		rep(i, 1, m) w[i] = 0;
		rep(i, 1, n) w[rk[x][rk[y][i]]]++;
		rep(i, 1, m) w[i] += w[i - 1];
		per(i, n, 1) sa[w[rk[x][rk[y][i]]]--] = rk[y][i];
		for (int i = m = 1; i <= n; i++)
		{
			int *a = rk[x] + sa[i], *b = rk[x] + sa[i - 1];
			rk[y][sa[i]] = *a == *b&&*(a + z) == *(b + z) ? m - 1 : m++;
		}
	}

	void getsa(int m)
	{
		//n = strlen(s + 1);
		rk[1][0] = now = sa[0] = s[0] = 0;
		rep(i, 1, m) w[i] = 0;
		rep(i, 1, n) w[s[i]]++;
		rep(i, 1, m) rk[1][i] = rk[1][i - 1] + (bool)w[i];
		rep(i, 1, m) w[i] += w[i - 1];
		rep(i, 1, n) rk[0][i] = rk[1][s[i]];
		rep(i, 1, n) sa[w[s[i]]--] = i;

		rk[1][n + 1] = rk[0][n + 1] = 0;	//多组的时候容易出bug
		for (int x = 1, y = rk[1][m]; x <= n && y <= n; x <<= 1) getsa(x, y);
		for (int i = 1, j = 0; i <= n; h[rk[now][i++]] = j ? j-- : j)
		{
			if (rk[now][i] == 1) continue;
			int k = n - max(sa[rk[now][i] - 1], i);
			while (j <= k && s[sa[rk[now][i] - 1] + j] == s[i + j]) ++j;
		}
	}

	void getrmq()
	{
		h[n + 1] = h[1] = lg[1] = 0;
		rep(i, 2, n) rmq[i][0] = h[i], lg[i] = lg[i >> 1] + 1;
		for (int i = 1; (1 << i) <= n; i++)
		{
			rep(j, 2, n)
			{
				if (j + (1 << i) > n + 1) break;
				rmq[j][i] = min(rmq[j][i - 1], rmq[j + (1 << i - 1)][i - 1]);
			}
		}
	}

	int lcp(int x, int y)
	{
		int l = min(rk[now][x], rk[now][y]) + 1, r = max(rk[now][x], rk[now][y]);
		return min(rmq[l][lg[r - l + 1]], rmq[r - (1 << lg[r - l + 1]) + 1][lg[r - l + 1]]);
	}

	void work()
	{
		GetS();	getsa(300);	getrmq();
		int ans = 1;
		rep(L, 1, n)
		{
			for (int i = 1; i + L <= n; i += L)
			{
				int R = lcp(i, i + L);
				ans = max(ans, R / L + 1);
				if (i >= L - R % L)
				{
					ans = max(lcp(i - L + R%L, i + R%L) / L + 1, ans);
				}
			}
		}
		printf("%dn", ans);
	}
}sa;

int main()
{
	T = read();
	while (T--) sa.work();
	return 0;
}