后缀数组四大基础应用

自用笔记算法

后缀数组

例题一

最长可重叠重复K次子串问题

输入

第一行两个整数 N和K。1≤N≤20000 1≤K≤N
接下来有 N 个整数，表示每个音的数字。1≤数字≤100

输出

一行一个整数，表示答案。

样例输入

8 2
1
2
3
2
3
2
3
1

样例输出

4

参考AC代码(int型)

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
#include <cstring>
#include<iostream>
#include <algorithm>
using namespace std;
const int N = 1000050;   
int sa[N],Rank[N],Rank2[N],height[N],cnt[N*50],*x,*y,n,k; 
int str[N];  
void radix_sort(int n,int sz)  
{  
    memset(cnt,0,sizeof(int)*sz);  
    for(int i=0;i<n;i++)  
        cnt[ x[ y[i] ] ]++;  
    for(int i=1;i<sz;i++)  
        cnt[i] += cnt[i-1];  
    for(int i=n-1;i>=0;i--)  
        sa[ --cnt[ x[ y[i] ] ] ] = y[i];  
} 
void get_sa(int text[],int n,int sz=1000001)  
{  
    x = Rank, y = Rank2;  
    for(int i=0;i<n;i++)  
        x[i] = text[i], y[i] = i;  
    radix_sort(n,sz);  
    for(int len=1;len<n;len<<=1)  
    {  
        int yid = 0;  
        for(int i=n-len;i<n;i++)  
            y[yid++] = i;  
        for(int i=0;i<n;i++)  
            if(sa[i] >= len)  
                y[yid++] = sa[i] - len;  
        radix_sort(n,sz);  
        swap(x,y);  
        x[ sa[0] ] = yid = 0;  
        for(int i=1;i<n;i++)  
        {  
            if(y[ sa[i-1] ]==y[ sa[i] ] && sa[i-1]+len<n && sa[i]+len<n && y[ sa[i-1]+len ]==y[ sa[i]+len ])  
                x[ sa[i] ] = yid;  
            else  
                x[ sa[i] ] = ++yid;  
        }  
        sz = yid + 1;  
        if(sz >= n)  
            break;  
    }  
    for(int i=0;i<n;i++)  
        Rank[i] = x[i];  
}  
 
void get_height(int text[],int n)  
{  
    int k = 0;  
    for(int i=0;i<n;i++)  
    {  
        if(Rank[i] == 0)  
            continue;  
        k = max(0,k-1);  
        int j = sa[ Rank[i]-1 ];  
        while(i+k<n && j+k<n && text[i+k]==text[j+k])  
            k++;  
        height[ Rank[i] ] = k;  
    }  
}   
bool set(int mid,int n,int k)  
{  
    for(int st=0,ed;st<n;st=ed)  
    {  
        ed = st + 1;  
        while(ed < n && height[ed] >= mid)  
            ed++;  
        if(ed - st >= k)  
            return true;  
    }  
    return false;  
}  
int main() 
{
    while(cin>>n>>k)
	{
		for(int i=0;i<n;i++)  
			scanf("%d",&str[i]);  
		get_sa(str,n);  
		get_height(str,n);  
		int l=0,r=n,mid;
		while (l < r)
		{
			mid = (l + r + 1) >> 1;
			if (set(mid,n,k)) 
				l = mid;
			else 
				r = mid - 1;
		}
		printf("%d\n", l);
	}
}

例题二

最长不可重叠重复子串问题

输入

第一行一个整数 N。1≤N≤100000
接下来有 N 个整数，表示每个音的数字。1≤数字≤1000

输出

一行一个整数，表示答案。

样例输入

8
1 2 3 2 3 2 3 1

样例输出

2

参考AC代码(int型)

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<iostream>
#include<algorithm>
using namespace std;
const int mx=1e5+5;
int s[mx],sa[mx],t[mx],t2[mx],c[mx],n;      //s为输入数组 sa为后缀数组 ank为名次数组
int ank[mx],height[mx];                      //height为相邻公共前缀数组
int minsa,maxsa;
void build_sa(int m)
{
    int i,*x=t,*y=t2;
    for (i=0;i<m;i++) c[i]=0;
    for (i=0;i<n;i++) c[x[i]=s[i]]++;
    for (i=1;i<m;i++) c[i]+=c[i-1];
    for (i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for (int k=1;k<=n;k<<=1)
    {
        int p=0;
        for (i=n-k;i<n;i++) y[p++]=i;
        for (i=0;i<n;i++) if (sa[i]>=k) y[p++]=sa[i]-k;
        for (i=0;i<m;i++) c[i]=0;
        for (i=0;i<n;i++) c[x[y[i]]]++;
        for (i=1;i<m;i++) c[i]+=c[i-1];
        for (i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;
        x[sa[0]]=0;
        for (i=1;i<n;i++)
        x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        if (p>=n) break;
        m=p;
    }
}
void getHeight()
{
    int i,j,k=0;
    for (i=0;i<n;i++) ank[sa[i]]=i;
    for (i=0;i<n;i++)
    {
        if (k) k--;
        int j=sa[ank[i]-1];
        while (s[i+k]==s[j+k]) k++;
        height[ank[i]]=k;
    }
}
void Init() 
{
    cin>>n;
	for(int i=0;i<n;i++)
		cin>>s[i];
}
bool check(int K)
{
    for(int i=1;i<=n;i++)
    if(height[i]< K)
    {
        minsa=sa[i];
        maxsa=sa[i];
    }
    else 
    {
        minsa=min(minsa,sa[i]);
        maxsa=max(maxsa,sa[i]);
        if(maxsa-minsa>=K)return true;
    }
    return false;
}
int main()
{
	Init();
    build_sa(1001);
	getHeight();
	int l,r,mid;
	l = 0; r = n /*>> 1*/;
	while (l < r)
	{
		mid = (l + r + 1) >> 1;
		if (check(mid)) 
			l = mid;
		else 
			r = mid - 1;
	}
	printf("%d\n", l);
	return 0;
}

例题三

最长公共子串问题

输入

共两行。一行一个仅包含小写字母的字符串。字符串长度不超过 100000。

输出

一行一个整数，表示答案。

样例输入

abcdefg
abacabca

样例输出

3

参考AC代码(char型)

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
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN = 4e5+1e3;
char s[MAXN];
int sa[MAXN], wa[MAXN], wb[MAXN], cnt[MAXN];
int rnk[MAXN], hi[MAXN], l1, l2;
bool equal(int *r,int a, int b, int k) 
{
	return r[a]==r[b]&&r[a+k]==r[b+k];
}
void DA(int n, int m) 
{
	int *x=wa, *y=wb, i, j, p;
	for(i=0; i<m; ++i) cnt[i]=0;
	for(i=0; i<n; ++i) ++cnt[x[i]=s[i]];
	for(i=1; i<m; ++i) cnt[i]+=cnt[i-1];
	for(i=n-1; i>-1; --i) sa[--cnt[x[i]]] = i;
	for(j=1; j<=n; j<<=1) {
		p=0;
		for(i=n-j; i<n; ++i) y[p++] = i;
		for(i=0; i<n; ++i) if(sa[i]>=j)
		   y[p++] = sa[i]-j;	
		for(i=0; i<m; ++i) cnt[i]=0; 
		for(i=0; i<n; ++i) ++cnt[x[i]];
		for(i=1; i<m; ++i) cnt[i]+=cnt[i-1];
		for(i=n-1; i>-1; --i) sa[--cnt[x[y[i]]]] = y[i];
		swap(x,y);
		m = 1;
		x[sa[0]] = 0;
		for(i=1;i<n; ++i)
			x[sa[i]] = equal(y,sa[i-1],sa[i],j)?m-1:m++;
		if(m==n) break;
	}
}
void calheight(int n) {
	int i, j, k;
	for(i=0; i<n; ++i) rnk[sa[i]] = i; 
	for(i=k=0; i<n-1; ++i) {
		if(k) --k;
		j = sa[rnk[i]-1];
		while(s[i+k]==s[j+k]) ++k;
		hi[rnk[i]] = k;
	}
}
int main() 
{
	int n;
	scanf("%s", s);
	l1 = strlen(s);
	s[l1] = '#';
	scanf("%s", s+l1+1);
	l2 = strlen(s+l1+1);
	n = l1+l2+1;
	DA(n, 130);
	calheight(n);
	int res = 0;
	for(int i=1; i<n-1; ++i)
		if((sa[i-1]<l1)^(sa[i]<l1))
			res = max(res, hi[i]);
	printf("%d\n", res);
	return 0;
}

例题四

重复次数最多的连续字串

输入

一行一个仅包含小写字母的字符串。字符串长度不超过 100000。

输出

一行一个整数，表示答案k。

样例输入

babbabaabaabaabab

样例输出

4

参考AC代码(char型)

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
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100005
int wa[N],wb[N],wv[N],ws[N];
int sa[N],rk[N],height[N];
char s[N];
void da(int n)
{
    int i,j,p,*x=wa,*y=wb,m=128;
    for(i=0;i<m;i++)ws[i]=0;
    for(i=0;i<n;i++)ws[x[i]=s[i]]++;
    for(i=1;i<m;i++)ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p){
        for(p=0,i=n-j;i<n;i++)y[p++]=i;
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        for(i=0;i<n;i++)wv[i]=x[y[i]];
        for(i=0;i<m;i++)ws[i]=0;
        for(i=0;i<n;i++)ws[wv[i]]++;
        for(i=1;i<m;i++)ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i];
        for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j])?p-1:p++;
    }
}
void calheight(int n)
{
    int i,j,k=0;
    for(i=1;i<=n;i++)rk[sa[i]]=i;
    for(i=0;i<n;height[rk[i++]]=k)
        for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
}
int lcp[N][32];
void init(int n)
{
    for(int i=1;i<=n;i++)lcp[i][0]=height[i];
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            lcp[j][i]=min(lcp[j][i-1],lcp[j+(1<<i-1)][i-1]);
}
int LCP(int a,int b)
{
    a--;b--;
    int l=min(rk[a],rk[b])+1,r=max(rk[a],rk[b]);
    int len=r-l+1,i;
    for(i=0;(1<<i)<=len;i++);
    i--;
    return min(lcp[l][i],lcp[r-(1<<i)+1][i]);
}
int get(int n)
{
    int ans=0;
    for(int l=1;l<=n;l++)
    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>0)
            ans=max(ans,LCP(i-l+r%l,i+r%l)/l+1);
    }
    return ans;
}
int main()
{
    scanf("%s",s);
    int n=strlen(s);
    da(n+1);
    calheight(n);
    init(n);
    printf("%d\n",get(n));
}

本文标题:后缀数组四大基础应用

文章作者:Hippopmonkey

发布时间:2016-11-21, 22:54:06

最后更新:2016-11-21, 23:09:52

原始链接:http://xuboming8.github.io/2016/11/21/后缀数组四大基础应用/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 后缀数组
    1. 1.1. 例题一
      1. 1.1.1. 输入
      2. 1.1.2. 输出
      3. 1.1.3. 样例输入
      4. 1.1.4. 样例输出
      5. 1.1.5. 参考AC代码(int型)
    2. 1.2. 例题二
      1. 1.2.1. 输入
      2. 1.2.2. 输出
      3. 1.2.3. 样例输入
      4. 1.2.4. 样例输出
      5. 1.2.5. 参考AC代码(int型)
    3. 1.3. 例题三
      1. 1.3.1. 输入
      2. 1.3.2. 输出
      3. 1.3.3. 样例输入
      4. 1.3.4. 样例输出
      5. 1.3.5. 参考AC代码(char型)
    4. 1.4. 例题四
      1. 1.4.1. 输入
      2. 1.4.2. 输出
      3. 1.4.3. 样例输入
      4. 1.4.4. 样例输出
      5. 1.4.5. 参考AC代码(char型)
|