后缀数组

  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的函数我按照论文里打了1~n,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);
}