后缀数组模版 及 可重叠和不可重叠最长重复子串【for_wind】
最近做了些机试题目，有道题目（不重复最长重复子串）测试时没想出有效解法，后来看到后缀数组，额，强大啊。记录之，分享之。有错误的地方，请留言啊，谢谢亲们~~~~~~~~~~~~~~~~~
概念部分，请查看参考资料2、3哦
//for_wind
一、后缀数组
（1）基本概念
1、字符串的大小比较：
关于字符串的大小比较，是指通常所说的 “ 字典顺序 ” 比较。如a<b，aab<ab，a<ab。
注：从字符串的大小比较的定义看，字符串s的所有后缀中任其中一对(u,v)不可能会相等，因为必要条件 len(u) ≠ len(v)不可能满足。所以任一字符串s中有len(s)个互不相同的后缀。我们可以将s的所有后缀排列，利用 后缀数组sa 与 名次数组rank 储存。
2、后缀数组sa：
将s的n个后缀从小到大排序后将 排序后的后缀的开头位置 顺次放入sa中，则sa[i]储存的是排第i大的后缀的开头位置。
- 简单的记忆就是“排第几的是谁”。
3、名次数组rank：
rank[i]保存的是suffix(i)｛后缀｝在所有后缀中从小到大排列的名次。则 若 sa[i]=j，则 rank[j]=i。
- 简单的记忆就是“你排第几”。
4、sa和rank的关系
对于 后缀数组sa 与 名次数组rank ，有 rank[ sa[i] ]=i
（这是很重要的一点，通过sa与rank的关系可以求出后缀数组）
- 由此可看出，后缀数组sa 与名次数组rank的关系为互逆关系。
Figure 1字符串aabaaaab的sa数组与rank数组
（2）倍增算法
1、主要思路：
倍增，s[i..i + 2^k − 1]的排名通过s[i..i + 2^(k − 1) − 1]和s[i + 2^(k − 1) − 1..i + 2^k] 的排名得到。
2、简要过程。
略。请参考最下面的参考资料3。嘻嘻。
Figure2倍增算法的计算过程
3、时间复杂度
每一趟的计数排序的时间复杂度是O(n)，排序的次数共log n次，总的时间复杂度为O(n log n)。
（3）最长公共前缀：
通常我们需要由rank与sa数组计算出一个辅助工具height数组——最长公共前缀(LCP)。
1、主要思想
height 数组： 定义height[i]=suffix(sa[i-1]) 和 suffix(sa[i]) 的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。
由height数组可得，对于j和k ，不妨设rank[j]<rank[k], 则有以下性质：
suffix(j) 和 suffix(k) 的最长公共前缀为 height[rank[j]+1],height[rank[j]+2], height[rank[j]+3], … ,height[rank[k]] 中的最小值。
以"aabaaaab"为例，求后缀"abaaaab"和后缀"aaab"的最长公共前缀，如图，可见其最长公共前缀等于1。
Figure3计算后缀"abaaaab"和后缀"aaab"的最长公共前缀
所以说，计算最长公共前缀是一个典型的RMQ问题。
2、关键性质
如何高效地计算后缀间的最长公共前缀呢？定义h[i]为suffix(i)和前一名次后缀的最长公共前缀{sa[ rank[ i ]-1 ]}。由性质可得，
h[i]>=h[i-1]-1
简单的证明如下：设suffix(k)是排在suffix(i-1)前一位的后缀，则它们的最长公共前缀显然是h[i-1]。那么，suffix(k+1)显然将排在suffix(i)的前面。并且，suffix(k+1)&suffix(i) 相对于 suffix(k)&suffix(i-1)来说就是同时去掉了第一位，即少了一位的匹配数。所以suffix(i)和前一名次后缀的最长公共前缀至少是h[i-1]-1。
显然，我们可以按照h数组的顺序计算height。
3、时间复杂度分析
求一次height后位数-1，一共有len(s)个后缀，所以只能退len(s)次，也就是说，求解的时间复杂度是O(len(s))。
（4）具体代码：
1、模版
/***********************************************
FileName : 后缀数组模版和相关算法
Description: 利用后缀数组，计算可重叠最长重复子串和不重叠最长重复子串
MainClasses: struct SuffixArray
Author and Time:for_wind [2014/4/16]
reference: https://www.byvoid.com/blog/lcs-suffix-array/
***********************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MAXLEN= 200; //输入字符串最大长度
const int MAXRANGE = 128;//输入字符串的字符范围 [0-127]
//后缀数组和相关算法
struct SuffixArray
{
struct RadixElement
{
int id; //下标
int k[2];//k[0](第一关键字排序)参考文献内图上的x; k[1]（第二关键字排序）图上的y
}RE[MAXLEN],RT[MAXLEN]; //RE[]关键成员；而RT[]仅用于RadixSort()函数中
int Len; //输入字符串A的长度Len
int A[MAXLEN]; //输入字符串A(已处理char to int)
int SA[MAXLEN]; //后缀数组SA
int Rank[MAXLEN]; //综合排名数组Rank：每个字符开始的长度为2k的子字符串进行排序
int Height[MAXLEN]; //Height数组：Height[i]是排名相邻的后缀SA[i]和SA[i-1]的最长公共前缀长度
int C[MAXRANGE]; //C[]仅用于RadixSort()函数中基数排序
//基数排序：总是按照最低有效位数字进行排序
//因此这里先第二关键字排序，后第一关键字排序
void RadixSort()
{
int i, y;
//先对第二关键字进行排序 y=1
//再对第一关键字进行排序 y=0
for (y=1; y>=0; y--)
{
memset(C, 0, sizeof(C));
for (i=1; i<=Len; i++) C[RE[i].k[y]]++;
for (i=1; i<MAXRANGE; i++) C[i] += C[i-1];
for (i=Len; i>=1; i--) RT[C[RE[i].k[y]]--] = RE[i];
for (i=1; i<=Len; i++) RE[i] = RT[i];
}
//构造排序后rank
for (i=1; i<=Len; i++)
{
Rank[ RE[i].id ] = Rank[ RE[i-1].id ];
if (RE[i].k[0]!=RE[i-1].k[0] || RE[i].k[1]!=RE[i-1].k[1])
Rank[ RE[i].id ]++;
}
}
//计算后缀数组的rank值
void CalcSA()
{
int i, k;
RE[0].k[0] = -1;
//---------第一次基数排序----------
for (i=1; i<=Len; i++)
{
RE[i].id = i; //初始下标
RE[i].k[0] = A[i]; //第一关键字设为字符值本身
RE[i].k[1] = 0; //第二关键字排序都设为0，对于长度为1的字符子串
}
RadixSort();
//---------剩余基数排序---------
for (k=1; k+1<=Len; k*=2) //k为子串长度，以2的指数增长
{
for (i=1; i<=Len; i++)
{
RE[i].id = i;//初始下标
RE[i].k[0] = Rank[i]; //第一关键字设为自己的rank值
RE[i].k[1] = i+k<=Len ? Rank[i+k] : 0; //第二关键字，未越界设为相应的位置i+k的Rank值，否则则设为0
}
RadixSort();
}
for (i=1; i<=Len; i++) //构造互逆关系
SA[ Rank[i] ] = i;
}
//计算后缀数组的height值（需要先调用CalcSA()）
void CalcHeight()
{
int i, k, h = 0;
for (i=1;i<=Len;i++)//依次计算(看起来：从长到短的后缀子串)
{
if (Rank[i] == 1) //排名为1，前面无元素，直接设h为0
h = 0;
else //
{
k = SA[Rank[i]-1]; //找到排序在它之前的后缀子串
if (--h < 0) h = 0; // 有关键性质： h[i]≥h[i-1]-1
for (; A[i+h]==A[k+h]; h++); //查找出公共长度
}
Height[Rank[i]] = h;
}
}
}SA;
char S[MAXLEN];
void init()
{
int i;
SA.Len = 0;
scanf("%s",S);
for (char *p=S; *p; p++) //char to int
{
SA.A[++SA.Len] = *p-'a'+1; //必须注意：输入字符串的字符范围
}
SA.A[SA.Len+1] = 0;
}
void Preprocess()
{
//预处理：构造后缀数组，计算rank和height
SA.CalcSA();
SA.CalcHeight();
}二、相关算法
1、可重叠最长重复子串
/***********************************************
FunctionName: int LRSOverlap()
Description: 可重叠最长重复子串
Mainideas：
首先求最长重复子串，等价于求两个后缀的最长公共前缀的最大值。
因为任意两个后缀的最长公共前缀都是height 数组里某一段的最小值，
那么这个值一定不大于height 数组里的最大值。所以最长重复子串的长度就是
height 数组里的最大值。
1、先使用预处理后的后缀数组SA
2、求出其height数组的最大值
Precondition: 需要先调用Preprocess()
Notice: 输出：排序后的后缀数组第一个符合要求的LRS
返回：可重叠最长重复子串的长度
Author and Time: for_wind [2014/4/16]
***********************************************/
int LRSOverlap()
{
int maxh = -1, maxindex = 0;
for(int i= 2; i<=SA.Len; i++)
{
if(SA.Height[i] > maxh)
{
maxh = SA.Height[i];
maxindex = SA.SA[i]; //该后缀子串的排序为i，起始位置为SA[i]
}
}
cout<<"--LRSOverlap--"<<endl;
cout<<"Possible LRS : ";
if(maxh <= 0)
{
cout<<"NULL!"<<endl;
return 0;
}
for(int i=maxindex; i<maxindex+maxh; ++i)
{
char temp = SA.A[i]+'a'- 1; //对应init()
cout<<temp;
}
cout<<endl;
cout<<"length : "<<maxh<<endl;
//cout<<"one is in A["<<maxindex-1<<"] ~ A["<<maxindex+maxh-1<<']'<<endl;
//cout<<endl;
return maxh;
}
int main()
{
while(1)
{
init();
Preprocess();
//-------利用预处理结果进行计算----
LRSOverlap();
//LRSNonOverlap();
//...
}
return 0;
}2、不重叠最长重复子串
//判断是否存在两个长度为k的子串是相同的，且不重叠
//不存在返回-1；否则返回符合要求的一个后缀子串的下标
int Check(int k, int n)
{
int i, imin = SA.SA[1], imax = SA.SA[1];
for(int i=2; i<=n; ++i)
{
if(SA.Height[i]<k)
{
imin = SA.SA[i];
imax= SA.SA[i];
}
else //存在公共前缀>=k
{
imin = imin < SA.SA[i] ? imin : SA.SA[i];
imax = imax > SA.SA[i] ? imax : SA.SA[i];
if(imax - imin>=k) //保证不重叠
return imin;
}
}
return -1;
}
/***********************************************
FunctionName: int LRSNonOverlap()
Description: 不重叠的最长重复子串
Mainideas：
1、先使用预处理后的后缀数组SA
2、二分判断是否存在相同前缀为k的，且不重叠的后缀子串
(k从Len/2开始递减)
Precondition: 需要先调用Preprocess()
Notice: 输出：排序后的后缀数组第一个符合要求的LRS
返回：可重叠最长重复子串的长度
Author and Time: for_wind [2014/4/17]
***********************************************/
int LRSNonOverlap()
{
//二分查找答案
int low = 0, mid, high = SA.Len/2;
int maxindex = -1;
while( low < high)
{
mid = (low + high + 1) / 2;
int tempindex = Check(mid, SA.Len);
if(tempindex != -1)//存在
{
low = mid;
maxindex = tempindex;
}
else
high = mid - 1;
}
cout<<"--LRSNonOverlap--"<<endl;
cout<<"Possible LRS : ";
if(low <= 0)
{
cout<<"NULL!"<<endl;
return 0;
}
for(int i = maxindex; i<maxindex+low; ++i)
{
char temp = SA.A[i]+'a'- 1; //对应init()
cout<<temp;
}
cout<<endl;
cout<<"length : "<<low<<endl;
return low;
}int main()
{
while(1)
{
init();
Preprocess();
//-------利用预处理结果进行计算----
//LRSOverlap();
LRSNonOverlap();
//...
}
return 0;
}3、暴力做法和较为暴力的做法
下面的代码中的基本算法中，
1、LRS_base_overlap和LRS_base_non_overlap是直接模拟，复杂度很高，具体分析见下面代码。
2、LRS_suffix_overlap虽然利用后缀数组，但只利用了其排序后的相邻关系（依次检测相邻的后缀子串的公共前缀，找出最大的）。
3、上面LRSOverlap()相关算法更快的原因：
（利用字符串的性质，计算并保存了rank和sa之间的关系，避免了多余的比较，这也是后缀数组的精华所在。个人认为哈。）
//for_wind [2014.4.16]
#include <iostream>
#include <string.h>
using namespace std;
const int MAX = 100;
//输出对应子串
void outputLRS(char *arr, int maxlen, int maxindex)
{
if(maxlen == 0)
{
cout<<"NULL LRS!"<<endl;
return;
}
for(int i= maxindex; i<maxlen+maxindex; i++)
cout<<arr[i];
cout<<endl;
}
//比较并返回子串元素的重复个数 O(N)
int comlen(char *p, char *q)
{
int len = 0;
while(*p & *q && *p++ == *q++)
{
++len;
}
return len;
}
//可重叠的基本最长重复子串算法 O(N*N*N)
void LRS_base_overlap(char arr[], int size)
{
int maxlen = 0;
int maxindex = 0;
for(int i=0; i<size; ++i)
{
for(int j=i+1; j<size; ++j)
{
int len = comlen(&arr[i],&arr[j]);
if(len > maxlen)
{
maxlen = len;
maxindex = i;
}
}
}
cout<<"LRS_base: "<<endl;
outputLRS(arr, maxlen, maxindex);
}
//比较函数 O(N)
int pstrcmp(const void *p, const void * q)
{
return strcmp(*(char**)p, *(char**)q);
}
//利用后缀数组，可重叠的最长重复子串算法 O(N*Nlog(N))
void LRS_suffix_overlap(char arr[], int size)
{
char *suff[MAX]; //后缀数组,其结构是一个字符指针数组，记录目标字符串的所有后缀的起始地址
int suff_index = 0, maxlen = 0, maxindex = 0;
for(int i=0; i<size; ++i)//初始化后缀数组 O(N)
{
suff[i] = &arr[i];
}
qsort(suff, size, sizeof(char *), pstrcmp); //排序后缀 O(N*Nlog(N))
for(int i=0; i<size-1; ++i) //依次检测相邻字符串 O(N*N)
{
int len = comlen(suff[i],suff[i+1]);
if(len > maxlen)
{
maxlen = len;
suff_index = i;
maxindex = i;
}
}
cout<<"LRS_suffix: "<<endl;
outputLRS(suff[suff_index],maxlen,0);
}
//不可重叠的基本最长重复子串算法 O(N*N*N)
void LRS_base_non_overlap(char arr[], int size)
{
int maxlen = 0;
int maxindex = 0;
char temparr[MAX];
strcpy(temparr, arr);
for(int i=0; i<size; ++i)
{
for(int len = size/2; len>0 && len+i<size; --len)
{
char temp = temparr[len+i];
temparr[len+i] = '\0';
for(int j=len+i; j<size; ++j)
{
if(strlen(&arr[j]) < len)
break;
if(comlen(temparr+i,&arr[j]) == len && maxlen < len)
{
maxlen = len;
maxindex = i;
}
}
temparr[len+i] = temp;
}
}
cout<<"LRS_base_non_overlap: "<<endl;
outputLRS(arr, maxlen, maxindex);
}
int main(void)
{
char arr[MAX]; //输入字符串
while(cin>>arr)
{
LRS_base_overlap(arr, strlen(arr));
LRS_suffix_overlap(arr, strlen(arr));
LRS_base_non_overlap(arr,strlen(arr));
//LRS_suffix_non_overlap(arr,strlen(arr));//利用后缀数组模版
}
return 0;
}