【POJ3261】milk patterns

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
这是后缀数组的其中一种简单应用。

1

题解：

知识点：

后缀数组，二分，LCP，离散化

分析：

按照罗穗骞的论文（《后缀数组—-处理字符串的有力工具》，IOI2009中国国家集训队论文集）中的说法，这种题型叫做:

可重叠的k 次最长重复子串

解决的方法是：先求出sa、height，然后二分长度$mid$，把一个求最大值问题转化成判定性问题。判定中，我们把height值大于等于$mid$的分组（即假如中间有一个height值小于mid，那么这个位置被分作下一组，然后再继续统计答案），假如一个组中的后缀个数大于等于$k$的话，这种情况就是成立的，然后继续缩小范围查找。

注意这道题的字符集大小太大了（虽然说数据太水了，不离散化也可以过），我们要先进行离散化，给字符重新定义一个值，然后再进行操作。

整个过程总的时间复杂度是：$O(n\log_{2}n)$

代码：

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=20010;
int n,m=20000,k,sa[maxn],a[maxn],_a[maxn],rnk[maxn],y[maxn],c[maxn],height[maxn],b[maxn],cnt;

int read()
{
    int x=0,ff=1;
    char cc=getchar();
    while (cc<48||cc>57)
        ff=cc=='-'?-1:1,cc=getchar();
    while (cc>=48&&cc<=57)
        x=(x<<1)+(x<<3)+(cc^48),cc=getchar();
    return x*ff;
}

void srt()
{
    int i;
    memset(c,0,sizeof(c));
    for (i=1;i<=n;i++)
        c[rnk[i]]++;
    for (i=2;i<=m;i++)
        c[i]+=c[i-1];
    for (i=n;i>=1;i--)
        sa[c[rnk[y[i]]]--]=y[i];
}

void getsa()
{
    int i,p=0,k;
    for (i=1;i<=n;i++)
    {
        rnk[i]=a[i];//因为已经离散化过了，所以可以直接用
        y[i]=i;
    }
    srt();
    for (k=1;p<n;m=p,k<<=1)
    {
        p=0;
        for (i=n-k+1;i<=n;i++)
            y[++p]=i;
        for (i=1;i<=n;i++)
            if (sa[i]>k)
                y[++p]=sa[i]-k;
        srt();
        swap(rnk,y);
        rnk[sa[1]]=p=1;
        for (i=2;i<=n;i++)
            rnk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
    }
}

void getheight()
{
    int i,k=0,j;
    for (i=1;i<=n;i++)
    {
        if (k)
            k--;
        j=sa[rnk[i]-1];
        while (a[i+k]==a[j+k])
            k++;
        height[rnk[i]]=k;
    }
}

bool check(int len)
{
    int tot=1,i;//因为第一个位置虽然height为0，但是也是有一个，所以初始值为1
    /*for (i=2;i<=n;i++)
    {
        if (height[i]<len)
        {
            if (tot>=k)
                return 1;
            tot=1;
        }
        else
            tot++;
    }
    return 0;*/
    for (i=2;i<=n;i++)
    {
        if (height[i]<len)
            tot=1;//如果不满足，就新开一个组
        else
            tot++;//否则就继续
        if (tot>=k)//已经成立就返回
            return 1;
    }
    return 0;
}

int getnum(int x)//二分查找最接近的值，可以用stl的lower_bound来代替，不过手写常数小
{
    int l=1,r=cnt,mid;
    while (l<=r)
    {
        mid=(l+r+1)>>1;
        if (b[mid]==x)
            return mid;
        if (b[mid]<x)
            l=mid+1;
        else
            r=mid-1;
    }
}

int main()
{
    int i,j;
    n=read();
    k=read();
    for (i=1;i<=n;i++)
        a[i]=read(),_a[i]=a[i];//另开一个空间来存离散的东西
    sort(_a+1,_a+n+1);
    for (i=1;i<=n;i++)
        if (i==1||_a[i]!=_a[i-1])
            b[++cnt]=_a[i];//去重，可以用一个stl函数代替
    for (i=1;i<=n;i++)
        a[i]=getnum(a[i]);//离散化
    getsa();
    getheight();
    int l=1,r=n,mid;
    while (l<r)//二分可行的长度
    {
        mid=(l+r+1)>>1;
        if (check(mid))
            l=mid;
        else
            r=mid-1;
    }
    printf("%d\n",l);
    return 0;
}
显示 Gitment 评论