后缀数组--切论文题

Apr. 21st, 2016


字符串 后缀数组 二分 RMQ 算法

这里的题目也都是论文《后缀数组——处理字符串的有力工具》这篇论文里带的,应该是比较全面了,除了用到后缀数组作为核心以外,在解决问题时还结合了RMQ问题、二分等思想。关键是,模板老敲错(i和j不分,=和==不分) =_=!

POJ-1743
题意:题目要求求出最长的两段相同旋律的长度,旋律要满足1.不同旋律不能有重叠的部分,2.代表旋律的一段数字可以加上或减去一个相同的数字,如果与另一段代表旋律的数字相同,也视为相同旋律,3.旋律长度最短为5
思路:求出所有相邻数字的差值,那么对于两段同样的旋律,差值一定相同,就转化成了求两个后缀的最长公共前缀的过程,同时要满足,对于长度为$k$的前缀,两个后缀的字符序相差要大于$k$,因为旋律不能有重叠的部分。
接下来二分这个最长的长度,由于是求差,所以只要$k\ge 4$即满足要求,假设差值串的长度为$n$,那么旋律长度最长为$(n-1)/2$,(这里分奇偶两种情况,最终结果一样),二分这个区间,对于每一个mid值都遍历整个height数组,找到符合条件的两个后缀即终止比较,取下一个mid值,二分和求后缀数组的复杂度都为$O(nlgn)$,也即最终的复杂度。
View Code in Github Repository

UVA-10298
题意:将一个字符串看作是由若干个子串不断重复得到的,求最长的重复次数。
思路:仍然是用height数组来解决。注意到这样一个事实,假设子串的长度为$k$,那么如果k的确可以重复从而得到整个字符串,那么$k$要满足两个要求,1.$k$要能够被字符串长度$l$整除。2.对于后缀suffix(0)和suffix(k),它们的最长公共前缀的长度应该为$n-k$。比如对于字符串$ababab$,后缀$ababab$和$abab$的最长公共前缀长度为4,即后一个后缀的长度。
因此,我们只需要穷举子串的长度,得到最大的符合要求的$k$值即可。穷举过程复杂度为$O(n)$,总复杂度取决于求后缀数组所使用的算法,最小为$O(n)$.
View Code in Github Repository

POJ-2774
题意:给定两个字符串,求它们的最长公共子串的长度。
思路:同样可以转化为求两个后缀的最长公共前缀的问题。首先将两个字符串连接起来,中间用一个比字符串中可能出现的字符的int数值都要小的数隔开(这样在排序的时候会排在原有字符串后缀的前面,方便求height数组)。求得height数组以后只需要遍历所有的height值求得最大值即可。但是要注意判断相关的两个后缀不能在同一个字符串中,复杂度为$O(n)$.
View Code in Github Repository

POJ-3294
题意:给出k个字符串,求出在超过k/2个字符串中都出现的最长公共子串,如果有多个,按照字典序输出
思路:首先将这$k$个字符串拼接起来,相邻两个字符串用不同的且比原各字符串中可能出现字符的int值都小的数字分割开来。得到height数组后,二分长度区间$[1,max_{1\le i\le k}(l_i)]$,在二分的过程中要注意几点。1.height数组从第$k+1$个值开始才有效,因为之前的值是那些以用于分割的数字为首字符的后缀的height数值,均为0。2.对于每一个height值对应的两个后缀,要通过遍历长度$k$来判断它们所在的字符串,并用一个布尔数组来判断该字符串是否已经被计算过。3.最后满足要求的后缀的数目如果大于$k/2$,就用数组将其中一个后缀的起始位置,即sa值记录下来,方便之后构造输出,如果有多个,依次记录即可。
由于按照height数组遍历的过程中,是从排名靠前的后缀开始寻找符合条件的公共子串,所以如果有多个,那么一定是按照字典序排列的。输出的时候注意截断的长度。
View Code in Github Repository

SPOJ-694
题意:给出一个字符串,找到它所有不同子串的个数。
思路:将一个长度为$n$,序号为$[0,n-1]$的字符串看作$n$个后缀,将它们按照字典序排列,对于第rank[1]个后缀,它将提供n-sa[1]个不同长度的子串,从第rank[2]个后缀开始,每个后缀都将提供n-sa[i]-height[i]个不同长度的子串,因为这个后缀可以提供的长度小于等于height[i]的子串已经被计算过了。遍历所有的后缀,将结果累加即可。复杂度为$O(n)$.
View Code in Github Repository

POJ-3261
题意:给定$n$个数,给定一个数$k$,求由这$n$个数构成的串中,重复次数不小于$k$的最长的子串的长度(子串可重叠)。
思路:仍然是先求出height数组,然后二分区间$[1,n]$。在二分的过程中,对于每一个mid值,都要求出最长公共前缀的长度大于等于mid的后缀的个数是否大于等于$k$,满足条件即修改mid值,注意边界。复杂度为$O(nlgn)$
根据height数组来二分区间的代码简直能当成模板来用了,代码段如下:

int low=1,high=n,mid;
while(low<=high) {
    mid=(low+high)/2;
    //printf("%d %d %d\n",low,mid,high);
    if(valid(mid,n,k)) {
        low=mid+1;
    } else {
        high=mid-1;
    }
}
//退出循环后符合要求的长度为low-1  
bool valid(int len,int n,int k) {
    int i=2,tmp;
    while(1) {
        tmp=1;
        if(i<=n&&height[i]<len) i++;
        if(i>n) break;
        while(i<=n&&height[i]>=len) {
            i++;
            tmp++;
        }
        if(tmp>=k) return true;
    }
    return false;
}  

View Code in Github Repository

URAL-1297
题意:啰嗦了一大堆,就是要求最长的回文字串,并输出这个子串;如果有多个长度相同的子串,求出最靠左的一个
思路:回文字串是从前往后和从后往前读都完全相同的字符串,用后缀数组来处理这种问题时,一般要将字符串翻过来,并拼接在原字符串后边,中间用一个比字符串中可能出现的字符的int数值都要小的数隔开。因为后缀数组不好处理前缀,翻转之后相当于把前缀变成了后缀,只要判断相应位置的两个后缀的最长公共前缀长度是否满足要求即可。
由于需要的两个后缀并不相邻,要求它们的最长公共前缀涉及到RMQ预处理,根据height数组,每次处理得到任意相邻$2^i$个后缀的最长公共前缀所在的下标值。总处理时间为$O(nlgn)$.
之后就开始处理回文串的问题,回文串分为偶串和奇串。 对于长度为$k$的奇串来说,满足$lcp(i,n-i-1)\ge (k+1)/2$,那么$i$为该奇串中间的位置 对于长度为$k$的偶串来说,满足$lcp(i,n-i)\ge k/2$,那么$i-1$和$i$为该偶串两个中间的位置 最后在输出时由于只需要输出一个串,所以直接把要输出串的后一个位置的字符置为'\0'即可(人工标记字符串的结束),从指定位置开始输出即可。 RMQ应用于height数组的预处理的代码直接当模板使吧:

void initRMQ(int n) {
     mm[0]=-1;
     for(int i=1;i<=n;i++)
         mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
     for(int i=1;i<=n;i++) best[0][i]=i;
     for(int i=1;i<=mm[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=mm[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和b的后缀的最长公共前缀
     a=rank[a];
     b=rank[b];
     if(a>b) swap(a,b);
     return height[askRMQ(a+1,b)];
}  

如对于数组$aabaaaab$,

它的height数组为 $height=[0,0,3,2,3,1,2,0,1]$

initRMQ()函数中,mm数组为 $mm=[-1,0,1,1,2,2,2,2,3]$,也即$mm[i]=\lfloor log_2 i\rfloor$

best数组为

$best[0]=[,1_1,2_2,3_3,4_4,5_5,6_6,7_7,8_8]$

$best[1]=[,1_{12},3_{23},3_{34},5_{45},5_{56},7_{67},7_{78}]$

$best[2]=[,1_{1234},5_{2345},5_{3456},7_{4567},7_{5678}]$

$best[3]=[,7_{12345678}]$

View Code in Github Repository

论文里还有几个题,有过思考,但是还没有想清楚做出来,决定先放一放,留作之后复习来用,先把题目贴在这里~~

POJ-3693重复次数最多的连续重复子串

POJ-3415长度不小于k的公共子串的个数

SPOJ-220每个字符串至少出现两次且不重叠的最长子串