本文共 8192 字,大约阅读时间需要 27 分钟。
8.3 最长公共子串
求N个串的最长公共子串,可以转化为求一些后缀的最长公共前缀的最大值,这些后缀应分属于N个串。设N个串分别为S1,S2,S3,…,SN。
具体方法如下:
1. 建立字符串S,使得S = S1[P1]S2[P2]S3…SN-1[PN-1]SN。其中P1,P2,…,PN-1应为不同的N - 1个不在字符集中的字符,作为分隔符。插入分隔符的目的是为了防止S的后缀的公共前缀超出原有串Si的范围。
2. 求出S的后缀数组及其Height数组。可以用倍增算法,或DC3算法。
3. 将S1,S2,S3,…,SN的公共子串大小至少为A的真假表示为check(A),如果check(A) == true那么对于任意A’(A’< A),都有check(A’) == true。故此,可以对区间[0, L]二分,从而找到最大的A,使得check(A)== true成立。其中L为S1,S2,S3,…,SN中最短的字符串的长度。可知,共需调用验证函数check()的次数为O(logL)。
4. check()函数的思想为:找出一个区间[i, j],使得对任意i ≤k ≤j均有Height[k] ≥A,同时S1,S2,S3,…,SN中每个字符串Sp,在[i, j]中均存在q,使得SA[q]原属于Sp,即(Pq-1在S中的下标)≤SA[q]≤ (Pq在S中的下标)。根据LCP定理,有LCP(i, j) ≥A。故此所有后缀SA[k](i≤k≤j)都有长度至少为A的共同前缀。进一步,由于分隔符的存在,S1,S2,S3,…,SN中所有的字符串都有长度至少为A的公共子串。
5. 寻找区间[i, j]的思想为:在区间[0, n-1]内向后枚举i,直至满足Height[i] ≥ A。然后在区间[i, n-1] 向后枚举j直至Height[i] ≥A不满足。其中n为S的长度。然判断区间[i, j]是否满足4.中条件。若满足条件,则check()函数返回true;不满足,则在区间[j, n-1]内继续向后枚举i和j,因为必有height[j] < A或者j > n-1。由于i, j只是扫描了一遍区间[0,n-1],可以知道寻找区间(即check()验证)的时间复杂度为O(n)。
8.3.1 实例
PKU JudgeOnline, 3450, Corporate Identity.
8.3.2 问题描述
给出一组字符串,求出它们的字典序最小的最长公共子串。
8.3.3 输入
3
aabbaabb
abbababb
bbbbbabb
2
xyz
abc
0
8.3.4 输出
abb
IDENTITY LOST
8.3.5 分析
bool check(int A)函数是用来判断一组字符串是不是有长度至少为A的公共子字串。findLeast()函数是check()的增强版,它在后者基础上找出了字典序最小的长度为A的公共子串。当然findLeast()比check()的速度慢,因为前者要找出所有长度至少为A的公共子串,并且从中取出字典序最小者。所以在二分A的时候,使用check()函数,在确定A的最大值之后则用findLeast()。
PKU JudgeOnline, 3080, Blue Jeans和这个题目几乎一样,只不过数据要弱很多。
8.3.6 程序
#include
#include
#include
using namespace std;
inline bool leq(int a1, int a2, int b1, int b2) { // lexic. orderfor pairs
return(a1< b1 || a1 == b1 && a2 <= b2);
} // and triples
inline bool leq(int a1, int a2, int a3, int b1, int b2, int b3) {
return(a1< b1 || a1 == b1 && leq(a2,a3, b2,b3));
}
// stably sort a[0..n-1] to b[0..n-1] with keys in 0..K fromr
static void radixPass(int* a, int* b, int* r, int n, int K)
{// count occurrences
int* c = new int[K + 1]; // counterarray
for (int i = 0; i<= K; i++) c[i] = 0; // resetcounters
for (int i = 0; i< n; i++) c[r[a[i]]]++; // countoccurences
for (int i = 0, sum = 0; i <= K; i++) { // exclusive prefix sums
int t =c[i]; c[i] = sum; sum += t;
}
for (int i = 0; i< n; i++) b[c[r[a[i]]]++] =a[i]; //sort
delete [] c;
}
// find the suffix array SA of s[0..n-1] in {1..K}^n
// require s[n]=s[n+1]=s[n+2]=0, n>=2
void suffixArray(int* s, int* SA, int n, int K) {
intn0=(n+2)/3, n1=(n+1)/3, n2=n/3, n02=n0+n2;
//n0是字符串中模为的下标的个数,n1,n2依此类推
int* s12 = new int[n02 + 3]; s12[n02]= s12[n02+1]= s12[n02+2]=0;
int* SA12 = new int[n02 + 3];SA12[n02]=SA12[n02+1]=SA12[n02+2]=0;
int* s0 = new int[n0];
int* SA0 = new int[n0];
// generatepositions of mod 1 and mod 2 suffixes
// the"+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
for (int i=0, j=0; i < n+(n0-n1); i++) if (i%3 != 0) s12[j++] = i;
//将所有模不为的下标存入s12中
// lsb radix sortthe mod 1 and mod 2 triples
radixPass(s12 , SA12, s+2, n02, K);
radixPass(SA12, s12 , s+1, n02, K);
radixPass(s12 , SA12, s , n02, K);
//radixPass实际是一个计数排序
//对后缀的前三个字符进行三次计数排序完成了对SA12数组的基数排序
//这个排序是初步的,没有将SA12数组真正地排好序,因为:
//若SA12数组中几个后缀的前三个字符相等,则起始位置靠后的排在后面
// findlexicographic names of triples
int name = 0,c0 = -1, c1 = -1, c2 = -1;
for (int i = 0; i< n02; i++) {
if(s[SA12[i]] != c0 || s[SA12[i]+1] != c1 || s[SA12[i]+2] != c2) {
name++; c0 = s[SA12[i]]; c1 =s[SA12[i]+1]; c2 = s[SA12[i]+2];
}
//name是计算后缀数组SA12中前三个字符不完全相同的后缀个数
//这么判断的原因是:SA12有序,故只有相邻后缀的前三个字符才可能相同
if (SA12[i]% 3 == 1) { s12[SA12[i]/3] = name; }// left half
else { s12[SA12[i]/3 + n0] = name;} // right half
//SA12[i]模不是就是,s12保存的是后缀数组SA12中前三个字符的排位
}
// recurse if names are not yet unique
if (name
//如果name等于n02,意味着SA12前三个字母均不相等,即SA12已有序
//否则,根据s12的后缀数组与SA12等价,对s12的后缀数组进行排序即可
suffixArray(s12, SA12, n02, name);
// store uniquenames in s12 using the suffix array
for (int i = 0; i< n02; i++) s12[SA12[i]] = i + 1;
} else // generate the suffix array of s12 directly
for (int i = 0; i< n02; i++) SA12[s12[i] - 1] = i;
//s12保存的是后缀数组SA12中前三个字符的排位
//在所有后缀前三个字符都不一样的情况下,s12就是后缀的排位
//至此SA12排序完毕
//SA12[i]是第i小的后缀的序号(序号从到n02),s12[i]是序号为i的后缀的排位
//使用后缀序号而不是实际位置的原因是递归调用suffixArray时不能保留该信息
// stably sort themod 0 suffixes from SA12 by their first character
for (int i=0, j=0; i < n02; i++) if (SA12[i] < n0) s0[j++] = 3*SA12[i];
//将SA12中所有的模为的后缀的实际位置减去按序存储在s0中
//注意后缀序号到实际位置的转化需将前者乘
//这意味着首先已经利用模为的后缀对SA0进行了初步排序
//只需要采用一次计数排序即可对SA0完成基数排序的最后一步
radixPass(s0, SA0, s, n0, K);
//最后一步,对有序表SA12和SA0进行归并
// merge sorted SA0suffixes and sorted SA12 suffixes
for (int p=0, t=n0-n1, k=0; k < n; k++) {
#define GetI() (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) *3 + 2)
int i =GetI(); // pos of current offset 12 suffix
int j =SA0[p]; // pos of current offset 0 suffix
if (SA12[t]< n0 ?
leq(s[i], s12[SA12[t] + n0], s[j], s12[j/3]) :
leq(s[i],s[i+1],s12[SA12[t]-n0+1],s[j],s[j+1],s12[j/3+n0]))
{ // suffix fromSA12 is smaller
SA[k] = i; t++;
if (t ==n02) { // done --- only SA0 suffixes left
for(k++; p < n0; p++, k++) SA[k] = SA0[p];
}
} else {
SA[k] = j; p++;
if (p ==n0) { // done--- only SA12 suffixes left
for(k++; t < n02; t++, k++) SA[k] = GetI();
}
}
}
delete []s12; delete [] SA12; delete[] SA0; delete [] s0;
}
void suffixArrayHeight(int *s, int *SA, int n, int K, int *rank, int *height)
{
int i, j,h;
for(i = 0;i < n; i++){
rank[SA[i]] = i;
//rank和SA互逆,即SA[rank[i]] == i&&rank[SA[i]] == i
}
h = 0;
for(i = 0;i < n; i++){
if(rank[i]== 0){
height[rank[i]] = 0;
}else{
j = SA[rank[i] - 1];
//如果用前缀的第一个字符的下标来标识前缀
//那么,j是前缀i == SA[rank[i]]的左邻前缀
while(s[i+ h] == s[j + h]){
h++;
//如果没有关于h[i]和h[i+1]的大小关系的定理,h需要从开始
}
height[rank[i]] = h;
//求出了h[i]的值
if(h> 0)
{
h--;
//h[i+1]的值大于或等于h[i]-1
}
}
}
}
#define maxStrNum 4001
#define maxStrLen 201
#define maxNum (maxStrNum * maxStrLen + 3)
int s[maxNum];
int SA[maxNum];
int rank[maxNum];
int height[maxNum];
int sequence[maxNum];//对应的字符串的序号
#define keyNum ('z' - 'a' + 1)
bool visited[maxStrNum];
char LCS[maxStrLen];
int n;
int N;
bool check(int A)
{
int i, j,k;
int temp;
if(A <=0)
return true;
for (i =1;i < n; i++)
{
//必有A>0,且height[0]==0,故此i可以不从开始
if(height[i]< A)
{
continue;
}
for(j =i + 1; j < n; j++)
{
if(height[j]< A)
{
break;
}
}
if(j -i + 1 < N)
{//不可能满足所有字符串都在区间[i - 1, j)中有对应的后缀SA[k]
i = j;
continue;
}
memset(visited, 0,sizeof(visited));
for(k =i - 1; k < j; k++){
//这里k必须从i-1开始而不是i开始,同时要防止i==0时越界
temp = sequence[SA[k]];
if(temp!= -1)
visited[temp] = true;
}
for(k =0; k < N; k++){
if(visited[k]== false)
{
break;
}
}
if(k ==N)
{
returntrue;
}
i = j;
//必有:height[j]< A || j == n
//这里不能i = j +1;,因为还有i++
}
return false;
}
bool findLeast(int A)
{
int i, j,k;
charstr[maxStrLen];
boolsuccess;
if(A <=0)
return true;
success = false;
for (i =1;i < n;i++)
{
//这里可以知道必有A>0,且height[0]==0
//故此i可以不从开始
if(height[i]< A)
{
continue;
}
for(j =i + 1; j < n; j++)
{
if(height[j]< A)
{
break;
}
}
if(j -i + 1 < N)
{//不可能满足所有字符串都在区间[i - 1, j)中有对应的后缀SA[k]
i = j;
continue;
}
memset(visited, 0,sizeof(visited));
for(k =i - 1; k < j; k++){
//这里k必须从i-1开始而不是i开始,同时要防止i==0时越界
if(k>= 0)
visited[sequence[SA[k]]] = true;
}
for(k =0; k < N; k++){
if(visited[k]== false)
{
break;
}
}
if(k ==N)
{
success = true;
for(k= 0; k < A; k++){
str[k] = s[SA[i] + k] + 'a' - 1;
}
str[A] = NULL;
if(LCS[0]== NULL || strcmp(str, LCS) < 0)
{
strcpy(LCS, str);
}
}
i = j;
//i = j + 1;
//必有:height[j]< A || j == n
}
returnsuccess;
}
int dichotomize(int top)
{
int low,high, mid;
low = 0;
high = top;
while(low +1 < high){
mid = (low + high) / 2;
if(check(mid))
low = mid;
elsehigh = mid - 1;
}
if(check(high))
low = high;
return low;
}
#define MAX 0x7FFFFFFF
int main()
{
int i, j;
int b;
int min;
charstr[maxStrLen];
int len;
int max;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d",&N)){
if(N ==0)
break;
n = 0;
memset(sequence, 0xFF, sizeof(sequence));
min = MAX;
for (i= 0; i < N; i++)
{
scanf("%s",str);
len = strlen(str);
if(min> len)
{
min = len;
}
for(j = 0; j < len; j++){
sequence[n] = i;
s[n++] = str[j] - 'a' + 1;
}
if(i < N - 1)
s[n++]= keyNum + i + 1;
}
b = keyNum + N - 1;
s[n] = s[n+1] = s[n+2] = SA[n] =SA[n+1] = SA[n+2] = 0;
suffixArray(s, SA, n, b);
suffixArrayHeight(s, SA, n, b, rank,height);
max = dichotomize(min);
if(max== 0){
cout << "IDENTITY LOST" << endl;
}else{
memset(LCS, 0, sizeof(LCS));
findLeast(max);
cout << LCS << endl;
}
}
return 1;
}本文章欢迎转载,请保留原始博客链接http://blog.csdn.net/fsdev/article
转载地址:https://blog.csdn.net/weixin_32473663/article/details/114749648 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!