SPOJ REPEATSRepeats

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

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("%d\n", ans); } }sa; int main() { T = read(); while (T--) sa.work(); return 0; }