后缀数组

OI&ACM, 字符串
  1. 模板
  2. 1 【poj 2774】Long Long Message
  3. 2 【poj 1743】Musical Theme
  4. 3 【poj 3294】Life Forms
  5. 4 【poj 3261】Milk Patterns

自己去看论文吧
其实我觉得两个log的sort也不错嘛
就是二分求LCP，然后比较LCP的后一位就可以知道两个串的大小关系，sort一下就好了

模板

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
#include<cstdio>
const int N=10001;
int r[N],sa[N],a[N],b[N],v[N],s[N],rank[N],height[N];
bool cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
	int i,j,p,*x=a,*y=b,*z;
	for(i=0;i<m;i++) s[i]=0;
	for(i=0;i<n;i++) s[x[i]=r[i]]++;
	for(i=1;i<m;i++) s[i]+=s[i-1];
	for(i=n-1;i>=0;i--) sa[--s[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++) v[i]=x[y[i]];
		for(i=0;i<m;i++) s[i]=0;
		for(i=0;i<n;i++) s[v[i]]++;
		for(i=1;i<m;i++) s[i]+=s[i-1];
		for(i=n-1;i>=0;i--) sa[--s[v[i]]]=y[i];
		for(z=x,x=y,y=z,p=1,x[sa[0]]=0,i=1;i<n;i++)
		  x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calheight(int *r,int *sa,int n)
{
	int i,j,k=0;
	for(i=0;i<n;i++) rank[sa[i]]=i;//论文1~n
	for(i=0;i<n;height[rank[i++]]=k)
	  for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}

1 【poj 2774】Long Long Message

求两个串最长公共子串的长度

求height的函数我按照论文里打了1n，WA了十几回，~ (>_<) ~~
改成0~n-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
#include<cstring>
#include<cstdio>
using namespace std;
const int N=200005;
int len,n,m=28,ans,sa[N],a[N],b[N],v[N],s[N],rank[N],height[N];
char r[N];
bool cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void DA()
{
	int i,j,p,*x=a,*y=b,*z;
	for(i=0;i<m;i++) s[i]=0;
	for(i=0;i<n;i++) s[x[i]=r[i]-'a'+1]++;
	for(i=1;i<m;i++) s[i]+=s[i-1];
	for(i=n-1;i>=0;i--) sa[--s[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++) v[i]=x[y[i]];
		for(i=0;i<m;i++) s[i]=0;
		for(i=0;i<n;i++) s[v[i]]++;
		for(i=1;i<m;i++) s[i]+=s[i-1];
		for(i=n-1;i>=0;i--) sa[--s[v[i]]]=y[i];
		for(z=x,x=y,y=z,p=1,x[sa[0]]=0,i=1;i<n;i++)
		  x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void getheight()
{
	for(int i=0;i<n;i++) rank[sa[i]]=i;
	for(int i=0,j,k=0;i<n;i++)
	{
		for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
		int x=sa[rank[i]],y=sa[rank[i]-1],z;
	  	if(x>y) z=x,x=y,y=z;
	  	if(y>len&&x+k<=len&&k>ans) ans=k;
	}  
}
int main()
{
	scanf("%s",r);
	len=strlen(r);
	r[len]='z'+1;
	scanf("%s",r+len+1);
	n=strlen(r);
	r[n++]='a'-1;
	DA();getheight();
	printf("%d\n",ans);
}

2 【poj 1743】Musical Theme

有N(1<=N<=20000)个音符的序列来表示一首乐曲，每个音符都是1~88范围内的整数，现在要找一个重复的主题。“主题”是整个音符序列的一个子串，它需要满足如下条件：
1.长度至少为5个音符。
2.在乐曲中重复出现。(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值)
3.重复出现的同一主题不能有公共部分。

我果断看不懂这题的英文。。。
求相邻两个的差，然后用后缀数组求不可重叠最长重复子串，详见论文 

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
#include<iostream>
#include<cstdio>
using namespace std;
const int N=20050;
int n,l,r,yes,mid,minn,maxx,sa[N],sum[N],a[N],b[N],v[N],s[N],rank[N],height[N];
bool cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int m)
{
	int i,j,p,*x=a,*y=b,*z;
	for(i=0;i<m;i++) s[i]=0;
	for(i=0;i<n;i++) s[x[i]=sum[i]]++;
	for(i=1;i<m;i++) s[i]+=s[i-1];
	for(i=n-1;i>=0;i--) sa[--s[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++) v[i]=x[y[i]];
		for(i=0;i<m;i++) s[i]=0;
		for(i=0;i<n;i++) s[v[i]]++;
		for(i=1;i<m;i++) s[i]+=s[i-1];
		for(i=n-1;i>=0;i--) sa[--s[v[i]]]=y[i];
		for(z=x,x=y,y=z,p=1,x[sa[0]]=0,i=1;i<n;i++)
		  x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calheight()
{
	int i,j,k=0;height[n]=0;
	for(i=0;i<n;i++) rank[sa[i]]=i;
	for(i=0;i<n;height[rank[i++]]=k)
	  for(k?k--:0,j=sa[rank[i]-1];sum[i+k]==sum[j+k];k++);
}
int main()
{
	while(scanf("%d",&n)&&n)
	{
		for(int i=0;i<n;i++) scanf("%d",&sum[i]);sum[n]=0; 
		for(int i=0;i<n;i++) sum[i]=sum[i+1]-sum[i]+90;
		n++;da(200);calheight();
		l=0;r=n/2;
		while(l<r)
		{
			mid=(l+r+1)/2;minn=N;maxx=0;yes=0;
			for(int i=1;i<=n;i++)
			{
				if(height[i]>=mid)
				{
					maxx=max(maxx,max(sa[i],sa[i-1]));
					if(sa[i])  minn=min(minn,sa[i]);
					if(sa[i-1])  minn=min(minn,sa[i-1]);
				}  
				else
				{
					if(maxx-minn>=mid) {yes=1;break;}
					minn=N;maxx=0;
				}
			}
			if(yes) l=mid;
			else r=mid-1;
		}
		if(l<4) l=0; else l++;
		printf("%d\n",l);
	} 
}

3 【poj 3294】Life Forms

给定n个字符串，求出现在大于n/2个字符串中的最长子串。

将n个字符串连起来，中间用不相同的且没有出现在字符串中的字符隔开，求后缀数组。然后二分答案，将后缀分成若干组，判断每组的后缀是否出现在大于n/2个的原串中。

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
#include<cstring>
#include<cstdio>
using namespace std;
const int N=110000;
int num,n,l,r,yes,mid,sum,len;
int f[N],g[N],sa[N],a[N],b[N],v[N],s[N],rank[N],height[N];
char str[N];
bool used[110];
bool cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int m)
{
	int i,j,p,*x=a,*y=b,*z;
	for(i=0;i<m;i++) s[i]=0;
	for(i=0;i<n;i++) s[x[i]=g[i]]++;
	for(i=1;i<m;i++) s[i]+=s[i-1];
	for(i=n-1;i>=0;i--) sa[--s[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++) v[i]=x[y[i]];
		for(i=0;i<m;i++) s[i]=0;
		for(i=0;i<n;i++) s[v[i]]++;
		for(i=1;i<m;i++) s[i]+=s[i-1];
		for(i=n-1;i>=0;i--) sa[--s[v[i]]]=y[i];
		for(z=x,x=y,y=z,p=1,x[sa[0]]=0,i=1;i<n;i++)
		  x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calheight()
{
	int i,j,k=0;height[n]=0;
	for(i=0;i<n;i++) rank[sa[i]]=i;
	for(i=0;i<n;height[rank[i++]]=k)
	  for(k?k--:0,j=sa[rank[i]-1];g[i+k]==g[j+k];k++);
}
int main()
{
	while(scanf("%d",&num)&&num)
	{
		n=0;
		for(int i=1;i<=num;i++)
		{
			scanf("%s",str);
			len=strlen(str);
			for(int j=0;j<len;j++)  g[n+j]=str[j]-'a'+1,f[n+j]=i;
			n+=len;
			f[n]=0;g[n++]=i+27;
		}
		g[n-1]=0;da(150);calheight();
		l=0;r=n;
		while(l<r)
		{
			mid=(l+r+1)/2;sum=0;yes=0;
			for(int i=1;i<=n;i++)
			{
				if(height[i]>=mid) 
				{
					int f1=f[sa[i]],f2=f[sa[i-1]];
					if(f1!=f2)
					{
						if(!used[f1]) sum++,used[f1]=1;
						if(!used[f2]) sum++,used[f2]=1;
					}
				}
				else
				{
					if(sum>num/2) {yes=1;break;}
					sum=0;memset(used,0,sizeof(used));
				}
			}
			if(yes) l=mid;
			else r=mid-1;
		}
		if(!l) printf("?\n\n");
		else
		{
			sum=0;
			for(int i=1;i<=n;i++)
			{
				if(height[i]>=l) 
				{
					int f1=f[sa[i]],f2=f[sa[i-1]];
					if(f1!=f2)
					{
						if(!used[f1]) sum++,used[f1]=1;
						if(!used[f2]) sum++,used[f2]=1;
					}
				}
				else
				{
					if(sum>num/2)
					{
						for(int j=sa[i-1];j<l+sa[i-1];j++)
				          printf("%c",g[j]+'a'-1);
				        printf("\n");
					}
					sum=0;memset(used,0,sizeof(used));
				}
			}
			printf("\n");
		}
	} 
}

4 【poj 3261】Milk Patterns

求出现次数大于等于k的子串的最长长度

可重叠的k次最长重复字串，论文19页
和上一题差不多，二分

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
#include<cstdio>
using namespace std;
const int N=20010;
int n,m=1000000,k,l,r,mid,sum,yes;
int g[N],sa[N],a[N],b[N],v[N],s[1000010],rank[N],height[N];
bool cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da()
{
	int i,j,p,*x=a,*y=b,*z;
	for(i=0;i<m;i++) s[i]=0;
	for(i=0;i<n;i++) s[x[i]=g[i]]++;
	for(i=1;i<m;i++) s[i]+=s[i-1];
	for(i=n-1;i>=0;i--) sa[--s[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++) v[i]=x[y[i]];
		for(i=0;i<m;i++) s[i]=0;
		for(i=0;i<n;i++) s[v[i]]++;
		for(i=1;i<m;i++) s[i]+=s[i-1];
		for(i=n-1;i>=0;i--) sa[--s[v[i]]]=y[i];
		for(z=x,x=y,y=z,p=1,x[sa[0]]=0,i=1;i<n;i++)
		  x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calheight()
{
	int i,j,k=0;height[n]=0;
	for(i=0;i<n;i++) rank[sa[i]]=i;
	for(i=0;i<n;height[rank[i++]]=k)
	  for(k?k--:0,j=sa[rank[i]-1];g[i+k]==g[j+k];k++);
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) scanf("%d",&g[i]);
	g[n++]=0;da();calheight();
	l=0;r=n;
	while(l<r)
	{
		mid=(l+r+1)/2;sum=0;yes=0;
		for(int i=1;i<=n;i++)
		{
			if(height[i]>=mid) 	sum++;
			else
			{
				if(sum>=k-1) {yes=1;break;}
				else sum=0;
			}
		}
		if(yes) l=mid;
		else r=mid-1;
	}
	printf("%d\n",l);
}
后缀数组