Repeats SPOJ - REPEATS

发表于 | 阅读数

给定一个字符串，求重复次数最多的连续重复子串

枚举长度$L$，然后求长度为$L$的子串最多能连续出现几次。
如果出现次数$\geq 2$,那么在枚举

1
2
for(int i=1;i+L<=len;i+=L)
    lcp(i,i+L);

一定会遇到那个循环节的一部分。

$L=3$

a b a a b a a b a
i i+L

$p=lcp(i,i+L)+L$,最小循环节的长度，重复次数$p/L$。

但是不能忘记还有剩余没有匹配的数$num=L-p\%L,$,然后重现计算$lcp(i-num+1,i-num+1+L)/L+1$

复杂度$O(n+n/2+n/3…n/n=nlogn)$

代码 
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int sa[N], ra[N], y[N], tn[N], he[N];
int rq[N][20];
void get_SA(char *s, int len, int size)
{
    int tmp[N]; //辅助数组
    for (int i = 1; i <= size; i++)
        tn[i] = 0;
    for (int i = 1; i <= len; i++)
        ra[i] = s[i], tn[ra[i]]++;
    for (int i = 1; i <= size; i++)
        tn[i] += tn[i - 1];
    for (int i = len; i >= 1; i--)
        sa[tn[ra[i]]--] = i;
    for (int k = 1; k <= len; k <<= 1)
    {

        int cnt = 0;
        for (int i = len - k + 1; i <= len; i++)
            y[++cnt] = i;
        for (int i = 1; i <= len; i++)
            if (sa[i] > k)
                y[++cnt] = sa[i] - k;

        for (int i = 1; i <= size; i++)
            tn[i] = 0;
        for (int i = 1; i <= len; i++)
            tn[ra[i]]++;
        for (int i = 1; i <= size; i++)
            tn[i] += tn[i - 1];
        for (int i = len; i >= 1; i--) //倒叙原因是因为tn[ra[y[i]]]是桶里面最大的
            sa[tn[ra[y[i]]]--] = y[i];
        for (int i = 1; i <= len; i++)
            tmp[i] = ra[i];

        cnt = 1;
        ra[sa[1]] = 1;
        for (int i = 2; i <= len; i++)
            ra[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + k] == tmp[sa[i - 1] + k]) ? cnt : ++cnt;
        if (cnt == len)
            break;
        size = cnt;
    }

    int k = 0;
    for (int i = 1; i <= len; i++)
        ra[sa[i]] = i;
    for (int i = 1; i <= len; i++)
    {
        if (k)
            k--;
        int j = sa[ra[i] - 1];
        while (i + k <= len && j + k <= len && s[j + k] == s[i + k])
            k++;
        he[ra[i]] = k;
    }
    for (int i = 1; i <= len; i++)
        rq[i][0] = he[i];
    for (int i = 1; (1 << i) <= len; i++)
        for (int j = 1; j + (1 << i) - 1 <= len; j++)
            rq[j][i] = min(rq[j][i - 1], rq[j + (1 << (i - 1))][i - 1]);
}
int len;
int lcp(int x, int y)
{
    if (x == y)
        return len - x + 1;
    x = ra[x], y = ra[y];
    if (x > y)
        swap(x, y);
    x++;
    int p = int(log(y - x + 1.0) * 1.0 / (1.0 * log(2)));
    return min(rq[x][p], rq[y - (1 << p) + 1][p]);
}
char s[N];
int T;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        int ans = 0;
        scanf("%d", &len);
        for (int i = 1; i <= len; i++)
        {
            char ss[2];
            scanf("%s", ss);
            s[i] = ss[0] - 'a' + 1;
        }

        get_SA(s, len, 3);
        for (int l = 1; l <= len; l++)
            for (int i = 1; i + l <= len; i += l)
            {
                int k = lcp(i, i + l);
                int tt = lcp(i, i + l) / l + 1;
                int ii = i - (l - k % l);
                if (ii > 0)
                    tt = max(tt, lcp(ii, ii + l) / l + 1);
                ans = max(tt, ans);
            }
        printf("%d\n", ans);
    }
}