先%罗DADA建议按照论文手推，更易明白
再%kuangbin大神
1、什么是后缀数组
后缀数组是后缀树的替代品，十分精巧，简洁
SA[]：后缀数组，按照后缀子串字典序进行排名
Rank[]：按照后缀子串长度由大到小进行排名
Height[]：两后缀之间的重复前缀长度
以下代码出自kuangbin与罗DADA的论文，略有改动
DA算法（倍增，O(nlogn)，空间复杂度6n）
/**kuangbin大神的栗子
*n = 8
*num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ }; 注意num最后一位为0，其他大于0
*rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 }; rank[0~n-1]为有效值，rank[n]必定为0无效值
*sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 }; sa[1~n]为有效值，sa[0]必定为n是无效值
*height[] = { 0, 0, 3, 2, 3, 1, 2, 0, 1 };
height[2~n]为有效值
**/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int M=20010;
int t1[M], t2[M, c[M]; //求SA数组的排序过程，所需要的的中间变量
//待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,
//除s[n-1]外的所有s[i]都大于0，r[n-1]=0
//函数结束以后结果放在sa数组中
bool cmp(int *r,int a,int b,int l)
{
return r[a] == r[b] && r[a+l] == r[b+l];
}
void da(int str[], int sa[], int Rank[], int height[], int n,int m)
{
n++;
int i, j, p;
int *x = t1; //用于第一关键字排序，相当于Rank[]数组
int *y = t2; //用于第二关键字排序，保存排序结果
//第一轮基数排序，如果s的最大值很大，可改为快速排序（第一关键字排序）
for(i = 0; i < m; i++) c[i] = 0;//清空c[]
for(i = 0; i < n; i++) c[x[i] = str[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(j = 1; j <= n; j <<= 1)
{
p = 0; //直接利用sa数组排序第二关键字
for(i = n-j; i < n; i++) y[p++] = i;//后面的j个数第二关键字为空的最小
for(i = 0; i < n; i++)
if(sa[i] >= j) y[p++] = sa[i] - j;
//基数排序第一关键字
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]; //根据sa和x数组计算新的x数组
/**
求出 sa 后，下一步是计算 rank 值。
可能有多个字符串的 rank 值是相同的，所以必须比较两个字符串是否完全相同，
并且 y 数组的值已经没有必要保存，为了节省空间，这里用 y 数组保存 rank值。
**/
swap(x, y); p=1; x[sa[0]]=0;
for(i = 1; i < n; i++)
x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p-1 : p++;
if(p >= n) break;
m = p;//下次基数排序的最大值
}
}
void Get_Height(int str[], int sa[], int Rank[], int Height[], int n)//计算Height值
{
int k = 0;
for(i = 0; i <= n; i++) Rank[sa[i]] = i;
for(i = 0; i < n; i++)
{
if(k) k--;
j = sa[Rank[i]-1];
while(str[i+k] == str[j+k]) k++;
height[Rank[i]] = k;
}
}
int Rank[MAXN], height[MAXN];
int RMQ[MAXN];
int Log[MAXN];
int best[20][MAXN];
void initRMQ(int n)
{
Log[0] = -1;
for(int i = 1; i <= n; i++)
Log[i]=((i&(i-1))==0) ? Log[i-1]+1 : Log[i-1];
for(int i = 1; i <=n; i++)
best[0][i] = i;
for(int i = 1; i <= Log[n]; i++)
for(int j=1; j+(1<<i)-1<=n; j++)
{
int a = best[i-1][j];
int b = best[i-1][j+(1<<(i-1))];
if(RMQ[a] < RMQ[b]) best[i][j] = a;
else best[i][j] = b;
}
}
int askRMQ(int a,int b)
{
int t;
t = Log[b-a+1];
b -= (1<<t)-1;
a = best[t][a];
b = best[t][b];
return RMQ[a] < RMQ[b] ? a : b;
}
int LCP(int a,int b)//最长公共子序列
{
a = Rank[a];
b = Rank[b];
if(a > b) swap(a,b);
return height[askRMQ(a+1, b)];
}
char str[MAXN];
int r[MAXN];
int sa[MAXN];
int main()
{
while(scanf("%s",str) == 1)
{
int len = strlen(str);
int n = 2*len + 1;
for(int i = 0; i < len; i++) r[i] = str[i]; //r[]负值
for(int i = 0; i < len; i++) r[len+1+i] = str[len-1-i];
r[len] = 1;
r[n] = 0;
da(r,sa,Rank,height,n,128);
Get_Height(r, sa, Rank, height, n);
for(int i=1; i<=n; i++) RMQ[i] = height[i];
/**以下是计算重复子序列**/
initRMQ(n);
int ans=0, st;
int tmp;
for(int i=0; i<len; i++)
{
tmp = LCP(i, n-i);//偶对称
if(2*tmp > ans)
{
ans = 2*tmp;
st = i-tmp;
}
tmp =LCP(i, n-i-1);//奇数对称
if(2*tmp-1 > ans)
{
ans=2*tmp-1;
st=i-tmp+1;
}
}
str[st+ans]=0;
printf("%s\n",str+st);
}
return 0;
}
DC3（分治，O(n)，空间复杂度10n）
将后缀分成两部分，第一部分是后缀 k%3！=0， 第二部分是后缀 k%3==0。（下标从零开始）
例如n=4
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2010;
#define F(x) ((x)/3+((x)%3==1?0:tb)) //计算原字符串 suffix(x)在新的字符串中的起始位置
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) //计算新字符串 suffix(x)在原字符串中的位置
//F(x)与G(x)为互逆运算
int wa[MAXN*3], wb[MAXN*3], wv[MAXN*3], wss[MAXN*3];//计算SA的过程数组
int c0(int *r,int a,int b) //比较是否完全相同
{
return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b) //比较后缀大小的函数
{
if(k == 2) return r[a]<r[b] || (r[a]==r[b] && c12(1,r,a+1,b+1));
else return r[a]<r[b] || ( r[a] == r[b] && wv[a+1]<wv[b+1] );
}
void sort(int *r,int *a,int *b,int n,int m) //基数排序
{
int i;
for(i = 0; i < n; i++) wv[i] = r[a[i]];
for(i = 0; i < m; i++) wss[i] = 0;
for(i = 0; i < n; i++) wss[wv[i]]++;
for(i = 1; i < m; i++) wss[i] += wss[i-1];
for(i = n-1; i >= 0; i--) b[--wss[wv[i]]] = a[i];
}
/*
ta： 下标i，满足 i%3==0 的个数
tb： 下标i，满足 i%3==1 的个数
tbc：下标i，满足 i%3!=0 的个数
*/
void dc3(int *r,int *sa,int n,int m)
{
int i, j, *rn = r+n;
int *san = sa+n, ta = 0, tb=(n+1)/3, tbc=0, p;
//起始位置模 3不等于 0 的后缀进行排序。
//用基数排序把 3 个字符“合并”成一个新的字符
r[n] = r[n+1] = 0;
for(i = 0; i < n; i++) if(i%3 != 0) wa[tbc++] = i;
sort(r+2, wa, wb, tbc, m);
sort(r+1, wb, wa, tbc, m);
sort(r, wa, wb, tbc, m); //基数排序结束后，新的字符的排名保存在 wb 数组中。
//求新的字符串时要判断两个字符组是否完全相同。
p=1, rn[F(wb(0))]=0;
for(i = 1; i < tbc; i++)
rn[F(wb[i])] = c0(r, wb[i-1], wb[i]) ? p-1 : p++;
//求san
if(p < tbc) dc3(rn, san, tbc, p);
else for(i = 0; i < tbc; i++) san[rn[i]] = i;
//起始位置模 3 等于 0 的后缀进行排序。
for(i = 0; i < tbc; i++) if(san[i] < tb) wb[ta++] = san[i]*3;
if(n%3 == 1) wb[ta++] = n - 1; //因为在 san 数组里并没有suffix(n)，要特殊处理
sort(r, wb, wa, ta, m);
//合并所有排序结果
for(i = 0; i < tbc; i++) wv[wb[i] = G(san[i])] = i;
i = 0, j = 0;
for(p = 0; i < ta && j < tbc; p++)
sa[p] = c12(wb[j]%3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
for(; i < ta; p++)sa[p] = wa[i++];
for(; j < tbc; p++)sa[p] = wb[j++];
} //str和sa也要三倍
void Get_Height(int str[],int sa[],int Rank[],int height[],int n)
{
int i,j,k = 0;
for(i = 0; i <= n; i++) Rank[sa[i]] = i;
for(i = 0; i < n; i++)
{
if(k) k--;
j = sa[Rank[i]-1];
while(str[i+k] == str[j+k]) k++;
height[Rank[i]] = k;
}
}
void solve(int str[],int sa[],int Rank[],int height[],int n,int m)
{
for(int i = n; i < n*3; i++) str[i] = 0;
dc3(str, sa, n+1, m);
Get_Height(str, sa, Rank, height, n);
}
网友评论