Reku
0%

后缀数组复习

Posted on Edited on In Views: Valine:

http://hihocoder.com/problemset/problem/1403

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。 旋律可以表示为一段连续的数列，相似的旋律在原数列不可重叠，比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次，2 3 出现了两次，小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少？

我感觉hihocoder上讲的还是非常清楚的。 求出来\(height\)数组之后，就是一个二分，找到长度为\(k-1\)的子序列的最大最小值就可以了，非常的裸。

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
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
    const static int MAXN = 100000 + 10;
    int cnt[MAXN], tr[2][MAXN], ts[MAXN];
    int sa[MAXN], rk[MAXN], ht[MAXN], len;
    void construct(const int *s, int n, int m=256) {
        int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
        memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
        partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
        for (k=1;k<=n;k<<=1) {
            for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
            fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
            partial_sum(cnt,cnt+n+1,cnt);
            for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
            fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
            partial_sum(cnt,cnt+n+1,cnt);
            for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
            for (i=rk[sa[0]]=0;i+1<n;++i) {
                rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
            }
        }
        for (i=0,k=0;i<n;++i) {
            if (!rk[i]) continue;
            for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
            ht[rk[i]]=k; if (k) k--;
        }
        rmq_init(n);
    }
    inline int lcp(int a, int b) {
        a=rk[a],b=rk[b];
        if (a == b) return len - a + 1;
        if (a>b) swap(a,b);
        return rmq(a+1,b);
    }
private:
    int mx[MAXN][20], LOG[MAXN];
    void rmq_init(int n) {
        for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
        for (int i=0;i<n;++i) mx[i][0]=ht[i];
        for (int i,j=1;(1<<j)<n;++j) {
            for (i=0;i+(1<<j)<=n;++i)
                mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
    }
    inline int rmq(int a, int b) {
        int k=LOG[b-a+1];
        return min(mx[a][k],mx[b-(1<<k)+1][k]);
    }
} nico;
int n,k;
int u[20010]={};
bool pan(int x,int y)
{
	int num=0;
	for(int i=1;i<n;i++)
	{
		if(nico.ht[i]>=x) num++;
		else num=0;
		if(num>=y) return 1;
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&u[i]);
	}
	nico.construct(u,n,256);
	k--;
	int l=0;
	int r=n;
	while(l<r)
	{
		int mid=(l+r)/2+1;
		if(pan(mid,k)) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
	return 0;
}

http://hihocoder.com/problemset/problem/1407

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。 旋律可以表示为一段连续的数列，相似的旋律在原数列不可重叠，比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次，2 3 出现了两次，小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少？

因为两次这个情况非常特殊，所以我们可以把字典序相邻的，整体公共前缀长度\(>k\)的打包，然后求一下最近的位置\(ma\)和最远的位置\(mi\)，用\(ma-mi>=k\)来判断这个公共前缀是否重复两次。

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
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
    const static int MAXN = 100000 + 10;
    int cnt[MAXN], tr[2][MAXN], ts[MAXN];
    int sa[MAXN], rk[MAXN], ht[MAXN], len;
    void construct(const int *s, int n, int m=256) {
        int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
        memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
        partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
        for (k=1;k<=n;k<<=1) {
            for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
            fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
            partial_sum(cnt,cnt+n+1,cnt);
            for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
            fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
            partial_sum(cnt,cnt+n+1,cnt);
            for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
            for (i=rk[sa[0]]=0;i+1<n;++i) {
                rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
            }
        }
        for (i=0,k=0;i<n;++i) {
            if (!rk[i]) continue;
            for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
            ht[rk[i]]=k; if (k) k--;
        }
        rmq_init(n);
    }
    inline int lcp(int a, int b) {
        a=rk[a],b=rk[b];
        if (a == b) return len - a + 1;
        if (a>b) swap(a,b);
        return rmq(a+1,b);
    }
    bool pan(int k,int n)
	{
		int ma,mi;
		for(int i=0;i<n;i++)
		{
			if(ht[i]<k)
			{
				ma=sa[i];
				mi=sa[i];
			}
			else
			{
				ma=max(ma,sa[i]);
				mi=min(mi,sa[i]);
				if(ma-mi>=k) return 1;
			}
		}
		return 0;
	}
private:
    int mx[MAXN][20], LOG[MAXN];
    void rmq_init(int n) {
        for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
        for (int i=0;i<n;++i) mx[i][0]=ht[i];
        for (int i,j=1;(1<<j)<n;++j) {
            for (i=0;i+(1<<j)<=n;++i)
                mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
    }
    inline int rmq(int a, int b) {
        int k=LOG[b-a+1];
        return min(mx[a][k],mx[b-(1<<k)+1][k]);
    }
} nico;
int n;
int u[100010]={};
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&u[i]);
	}
	nico.construct(u,n,256);
	int l=0;
	int r=n;
	while(l<r)
	{
		int mid=(l+r)/2+1;
		if(nico.pan(mid,n)) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
	return 0;
}

http://hihocoder.com/problemset/problem/1415

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有共同的部分。 旋律是一段连续的数列，如果同一段旋律在作品A和作品B中同时出现过，这段旋律就是A和B共同的部分，比如在abab 在 bababab 和 cabacababc 中都出现过。小Hi想知道两部作品的共同旋律最长是多少？

思路比较显然，就是把字符串合起来排个序，然后判断一下相邻字典序的后缀是不是属于两个串，感觉也可以推广到多个串？

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
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
    const static int MAXN = 300000 + 10;
    int cnt[MAXN], tr[2][MAXN], ts[MAXN];
    int sa[MAXN], rk[MAXN], ht[MAXN], len;
    void construct(const char *s, int n, int m=256) {
        int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
        memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
        partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
        for (k=1;k<=n;k<<=1) {
            for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
            fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
            partial_sum(cnt,cnt+n+1,cnt);
            for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
            fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
            partial_sum(cnt,cnt+n+1,cnt);
            for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
            for (i=rk[sa[0]]=0;i+1<n;++i) {
                rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
            }
        }
        for (i=0,k=0;i<n;++i) {
            if (!rk[i]) continue;
            for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
            ht[rk[i]]=k; if (k) k--;
        }
        rmq_init(n);
    }
    inline int lcp(int a, int b) {
        a=rk[a],b=rk[b];
        if (a == b) return len - a + 1;
        if (a>b) swap(a,b);
        return rmq(a+1,b);
    }
    bool pan(int k,int n)
	{
		int ma,mi;
		for(int i=0;i<n;i++)
		{
			if(ht[i]<k)
			{
				ma=sa[i];
				mi=sa[i];
			}
			else
			{
				ma=max(ma,sa[i]);
				mi=min(mi,sa[i]);
				if(ma-mi>=k) return 1;
			}
		}
		return 0;
	}
private:
    int mx[MAXN][20], LOG[MAXN];
    void rmq_init(int n) {
        for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
        for (int i=0;i<n;++i) mx[i][0]=ht[i];
        for (int i,j=1;(1<<j)<n;++j) {
            for (i=0;i+(1<<j)<=n;++i)
                mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
    }
    inline int rmq(int a, int b) {
        int k=LOG[b-a+1];
        return min(mx[a][k],mx[b-(1<<k)+1][k]);
    }
} nico;
string a,b;
char *c;
int n;
int t;
int main()
{
	cin>>a>>b;
	t=a.size();
	a=a+'#'+b;
	n=a.size();
	c=(char*)a.data();
	nico.construct(c,n,256);
	int ans=0;
	for(int i=1;i<n;i++)
	{
		if(nico.sa[i]>t&&nico.sa[i-1]<t) ans=max(ans,nico.ht[i]);
		if(nico.sa[i]<t&&nico.sa[i-1]>t) ans=max(ans,nico.ht[i]);
	}
	cout<<ans<<endl;
	return 0;
}

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。 我们把一段旋律称为(k,l)-重复的，如果它满足由一个长度为l的字符串重复了k次组成。 如旋律abaabaabaaba是(4,3)重复的，因为它由aba重复4次组成。 小Hi想知道一部作品中k最大的(k,l)-重复旋律。

http://hihocoder.com/problemset/problem/1419 神奇的结论！

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
#include <bits/stdc++.h>
using namespace std;
struct SuffixArray {
public:
    const static int MAXN = 100000 + 10;
    int cnt[MAXN], tr[2][MAXN], ts[MAXN];
    int sa[MAXN], rk[MAXN], ht[MAXN], len;
    void construct(const char *s, int n, int m=256) {
        int i,j,k,*x=tr[0],*y=tr[1]; this->len = n;
        memset(cnt,0,sizeof(cnt[0])*m); for (i=0;i<n;++i) cnt[s[i]]++;
        partial_sum(cnt,cnt+m,cnt); for (i=0;i<n;++i) rk[i]=cnt[s[i]]-1;
        for (k=1;k<=n;k<<=1) {
            for (i=0;i<n;++i) x[i]=rk[i],y[i]=i+k<n?rk[i+k]+1:0;
            fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[y[i]]++;
            partial_sum(cnt,cnt+n+1,cnt);
            for (i=n-1;i>=0;--i) ts[--cnt[y[i]]]=i;
            fill(cnt,cnt+n+1,0); for (i=0;i<n;++i) cnt[x[i]]++;
            partial_sum(cnt,cnt+n+1,cnt);
            for (i=n-1;i>=0;--i) sa[--cnt[x[ts[i]]]]=ts[i];
            for (i=rk[sa[0]]=0;i+1<n;++i) {
                rk[sa[i+1]]=rk[sa[i]]+(x[sa[i]]!=x[sa[i+1]]||y[sa[i]]!=y[sa[i+1]]);
            }
        }
        for (i=0,k=0;i<n;++i) {
            if (!rk[i]) continue;
            for (j=sa[rk[i]-1];i+k<n&&j+k<n&&s[i+k]==s[j+k];) k++;
            ht[rk[i]]=k; if (k) k--;
        }
        rmq_init(n);
    }
    inline int lcp(int a, int b) {
        a=rk[a],b=rk[b];
        if (a == b) return len - a + 1;
        if (a>b) swap(a,b);
        return rmq(a+1,b);
    }
    int ff()
    {
    	int ans=0;
    	for(int L=1;L<=len;L++)
		{
		    for (int i=0;i+L<len;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);
		        }
		    }
		}
		return ans;
	}
private:
    int mx[MAXN][20], LOG[MAXN];
    void rmq_init(int n) {
        for (int i=-(LOG[0]=-1);i<n;++i) LOG[i]=LOG[i>>1]+1;
        for (int i=0;i<n;++i) mx[i][0]=ht[i];
        for (int i,j=1;(1<<j)<n;++j) {
            for (i=0;i+(1<<j)<=n;++i)
                mx[i][j]=min(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
    }
    inline int rmq(int a, int b) {
        int k=LOG[b-a+1];
        return min(mx[a][k],mx[b-(1<<k)+1][k]);
    }
} nico;
int n,k;
char u[100010]={};
int main()
{
	scanf("%s",u);
	nico.construct(u,strlen(u),256);
	printf("%d\n",nico.ff());
	return 0;
}