Poj 3294 Life Forms (一)

本题练习后缀数组和LCP.二分查找长度是否满足条件即可。

后缀数组模板：

[cpp]
int sa[Maxn],t[Maxn],t2[Maxn],c[Maxn];
int rank[Maxn],height[Maxn];
//传递的两个参数：n是数组大小，m是数组内元素的Ascii码的最大值+1
void build_sa(int n,int m)
{
int i,*x = t,*y = t2;
//基数排序
for(i=0; i for(i=0; i for(i=1; i for(i = n-1; i>=0; i--) sa[--c[x[i]]] = i;
for(int k=1; k<=n; k<<=1)
{
int p = 0;
//直接利用sa数组排序第二关键字
for(i = n-k; i for(i = 0; 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 = 0; i < m; i++) c[i] += c[i-1];
for(i = n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];
//根据sa 和y数组计算新的x数组
swap(x,y);
p = 1;
x[sa[0]] = 0;
for(i=1; 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;
}
}
//注意getHeight传递入的参数是原数组的长度-1.切记
void getHeight(int n)
{
int i, j, k = 0;
for(i = 1; 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]; s[i + k] == s[j + k]; ++k);
return;
}

int sa[Maxn],t[Maxn],t2[Maxn],c[Maxn];
int rank[Maxn],height[Maxn];
//传递的两个参数：n是数组大小，m是数组内元素的Ascii码的最大值+1
void build_sa(int n,int m)
{
int i,*x = t,*y = t2;
//基数排序
for(i=0; i for(i=0; i for(i=1; i for(i = n-1; i>=0; i--) sa[--c[x[i]]] = i;
for(int k=1; k<=n; k<<=1)
{
int p = 0;
//直接利用sa数组排序第二关键字
for(i = n-k; i for(i = 0; 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 = 0; i < m; i++) c[i] += c[i-1];
for(i = n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];
//根据sa 和y数组计算新的x数组
swap(x,y);
p = 1;
x[sa[0]] = 0;
for(i=1; 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;
}
}
//注意getHeight传递入的参数是原数组的长度-1.切记
void getHeight(int n)
{
int i, j, k = 0;
for(i = 1; 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]; s[i + k] == s[j + k]; ++k);
return;
}本题要注意两点：getHeight(n)中传递的参数是数组长度-1，然后二分法的时候边界要小心，n=1时，直接输出原字符串即可。

[cpp]
#include
#include
#include
#include
#include
#include