后缀数组详细整理,后缀数组

题意

主题素材链接

uva11107

#35. 后缀排序

 统计

  •  描述
  •  提交
  •  自定义测量试验

这是一道模板题。

读入二个尺寸为 nn 的由小写印度语印尼语字母组成的字符串,请把那个字符串的全体非空后缀按字典序从小到大排序,然后按顺序输出后缀的率先个字符在原串中的地点。地点编号为 11 到 nn。

而外为了特别表达你真正有给后缀排序的超工夫,请别的输出 n−1n−1 个整数分别表示排序后相邻后缀的最长公共前缀的长度。

Sol

那题打死作者也不会想到后缀数组的,应该会全程想AC自动机之类的呢

但知道那题能用后缀数组做之后应该就不是那么难了

首先把\和\拼到一齐跑,求出Height数组

暴力枚举每种后缀是还是不是能成为答案。

具体来讲,每一次相比较当前后缀和\的lcp,假设长度\的话就从非法的职位延续协作

rmq维护一下区间lcp最小值

BZOJ上被完美卡常

// luogu-judger-enable-o2#include<bits/stdc++.h>using namespace std;const int MAXN = 2e5 + 10;const int INF = 2333;inline int read() {    char c = getchar(); int x = 0, f = 1;    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N, M, L, rak[MAXN], tax[MAXN], tp[MAXN], sa[MAXN], H[MAXN], f[MAXN][20], lg2[MAXN];char s[MAXN], s0[MAXN];void Qsort() {    for(int i = 0; i <= M; i++) tax[i] = 0;    for(int i = 1; i <= N; i++) tax[rak[i]]++;    for(int i = 1; i <= M; i++) tax[i] += tax[i - 1];    for(int i = N; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i];}void SuffixSort() {    for(int i = 1; i <= N; i++) rak[i] = s[i], tp[i] = i; M = 233; Qsort();    for(int w = 1, p = 0; p < N; w <<= 1, M = p) { p = 0;        for(int i = 1; i <= w; i++) tp[++p] = N - i + 1;        for(int i = 1; i <= N; i++) if(sa[i] > w) tp[++p] = sa[i] - w;        Qsort(); swap; rak[sa[1]] = p = 1;        for(int i = 2; i <= N; i++) rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++p;    }    for(int i = 1, k = 0; i <= N; i++) {        if k--; int j = sa[rak[i] - 1];        while(s[i + k] == s[j + k]) k++;        H[rak[i]] = k;    } }void Pre() {    for(int i = 1; i <= N; i++) f[i][0] = H[i];    for(int j = 1; j <= 17; j++)        for(int i = 1; i + (1 << j) - 1 <= N; i++) f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);}int Query(int x, int y) {    if swap; x++;    int k = lg2[y - x + 1];    return min(f[x][k], f[y - (1 << k) + 1][k]);}int check(int x, int y, int dep) {    if return Query(rak[x], rak[y]);    int num = Query(rak[x], rak[y]);    num +=  check(x + num + 1, y + num + 1, dep + 1) + 1;    return num;}void solve() {    scanf("%s%s", s + 1, s0 + 1);    L = strlen; N = strlen;    for(int i = 1; i <= L; i++) s[N + i] = s0[i];    N += L;    SuffixSort; N -= L; int ans = 0;    for(int i = 1; i <= N - L + 1; i++) if(check(i, N + 1, 0) >= L) ans++;    printf("%d\n", ans);}int main() {    //freopen("a.in", "r", stdin);    lg2[1] = 0; for(int i = 2; i <= MAXN - 1; i++) lg2[i] = lg2[i >> 1] + 1;    for(int T = read(); T; solve;    return 0;}/*2ATCGCCCTACTTCAATCGCCCTACTTCA*/

题意

输入 n 个 DNA 体系,求出长度最大的字符串,使得它在超越二分一的 DNA
类别中年花甲之年是出现。若是有多解,按字典序输出。

输入格式

一行叁个尺寸为 nn 的仅包括小写马耳他语字母的字符串。

分析

论文

后缀数组杰出题。加深多少个重大数组的印象。

和 poj2774
同样,都是要去老是字符串,保障分隔符无法和字符串内的字符同样,且无法重新。
为什么要连接呢?因为求后缀数组实际是对后缀字符串实行排序,那么有集体前缀子串的后缀字符串会尽大概的排在一同,不相同的相间符保障公共子串不会扩散到别的串上。而
height 数组对应的就是相邻 sa 数组的 lcp ( 最长公共前缀
)。依照选用的最大尺寸 m,能够将接二连三的且 lcp 长度当先等于 m
的后缀子串分到一组,要去掉这一个在同叁个原串里的子串,用多少个标识数组标志当前字符属于哪个原串。最终总括个数是不是超过二分之一就能够。

这种求最大、最小应该想到和二分法有关。

输出格式

第一行 n 个整数,第 i个整数表示排行为 i 的后缀的首先个字符在原串中的地点。

其次行 n−1 个整数,第 i 个整数表示名次为 i 和排行为 i+1 的后缀的最长公共前缀的长度。

code

#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
const int MAXN = 2e5 + 10;
char s[MAXN];
int sa[MAXN], t[MAXN], t2[MAXN], c[MAXN], n; // n 为 字符串长度 + 1,s[n - 1] = 0

int rnk[MAXN], height[MAXN];
// 构造字符串 s 的后缀数组。每个字符值必须为 0 ~ m-1
void build_sa(int m) {
    int i, *x = t, *y = t2;
    for(i = 0; i < m; i++) c[i] = 0;
    for(i = 0; i < n; i++) c[x[i] = s[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(int k = 1; k <= n; k <<= 1) {
        int p = 0;
        for(i = n - k; i < n; i++) y[p++] = i;
        for(i = 0; i < n; i++) if(sa[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];
        swap(x, y);
        p = 1; x[sa[0]] = 0;
        for(i = 1; i < n; 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;
    }
}
void getHeight() {
    int i, j, k = 0;
    for(i = 0; i < n; i++) rnk[sa[i]] = i;
    for(i = 0; i < n - 1; i++) {
        if(k) k--;
        j = sa[rnk[i] - 1];
        while(s[i + k] == s[j + k]) {
            k++;
        }
        height[rnk[i]] = k;
    }
}
// 保证 s[n-1] = 0 且前面非 0 // 也就是说空串在最前
// sa[0] = n - 1,sa[i] 有效的只有 [1, n-1] ( 因为前面的 n 加 1 了 )表示第 i 位的是谁( 以第几个字符开始的字符串后缀 )
// height[i] 有效的只有 [2, n-1] 表示 lcp(sa[i], sa[i-1]) 最长公共前缀
char s1[MAXN];
int id[MAXN];
int check(int c, int m) {
    set<int> S;
    S.insert(id[sa[1]]);
    for(int i = 2; i < n; i++) {
        while(i < n && height[i] >= m) {
            S.insert(id[sa[i]]);
            i++;
        }
        if(2 * S.size() > c) return 1;
        S.clear();
        S.insert(id[sa[i]]);
    }
    return 0;
}
void print(int c, int m) {
    set<int> S;
    S.insert(id[sa[1]]);
    for(int i = 2; i < n; i++) {
        while(i < n && height[i] >= m) {
            S.insert(id[sa[i]]);
            i++;
        }
        if(2 * S.size() > c) {
            int bgn = sa[i - 1];
            for(int j = 0; j < m; j++) {
                printf("%c", s[bgn + j]);
            }
            puts("");
        }
        S.clear();
        S.insert(id[sa[i]]);
    }
}
int main() {
    int c;
    int f = 1;
    while(scanf("%d", &c) && c) {
        memset(s, 0, sizeof s);
        if(!f) puts("");
        else f = 0;
        int bound = 1;
        for(int i = 0; i < c; i++) {
            scanf("%s", s1);
            int l = strlen(s), l1 = strlen(s1);
            for(int j = 0; j < l1; j++) {
                s[j + l] = s1[j];
                id[j + l] = i;
            }
            if(bound == 97) bound = 123;
            s[l + l1] = bound++; // 分隔符
            id[l + l1] = i;
            s[l + l1 + 1] = 0;
        }
        if(c == 1) {
            puts(s1); continue;
        }
        n = strlen(s) + 1; // 保证 s[n-1] = 0
        build_sa(128);
        getHeight();
        int l = 0, r = 1000, mid, ans = 0;
        while(l <= r) {
            mid = (l + r) / 2;
            if(check(c, mid)) { ans = mid; l = mid + 1; }
            else r = mid - 1;
        }
        if(ans == 0) puts("?");
        else print(c, ans);
    }
    return 0;
}

样例一

input

ababa

output

5 3 1 4 2
1 3 0 2

explanation

排序后结果为:

  1. a
  2. aba
  3. ababa
  4. ba
  5. baba

限定与约定

1≤n≤1051≤n≤105

岁月范围:1s1s

空间范围:256MB256MB

下载

样例数据下载

 

#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+7;
int len,maxx,sa[N],tsa[N],rank[N],trank[N],h[N],c[N];
char s[N];
void DA(){
    int p;
    memset(c,0,sizeof c);maxx=256;
    for(int i=1;i<=len;i++) c[rank[i]=s[i]]++;
    for(int i=2;i<=maxx;i++) c[i]+=c[i-1];
    for(int i=len;i;i--) sa[c[rank[i]]--]=i;
    trank[sa[1]]=p=1;
    for(int i=2;i<=len;i++){
        if(rank[sa[i]]!=rank[sa[i-1]]) p++;
        trank[sa[i]]=p;
    }
    for(int i=1;i<=len;i++) rank[i]=trank[i];
    for(int k=1;p<len;k<<=1,maxx=p){
        p=0;
        for(int i=len-k+1;i<=len;i++) tsa[++p]=i;
        for(int i=1;i<=len;i++) if(sa[i]>k) tsa[++p]=sa[i]-k;
        memset(c,0,sizeof c);
        for(int i=1;i<=len;i++) trank[i]=rank[tsa[i]];
        for(int i=1;i<=len;i++) c[trank[i]]++;
        for(int i=2;i<=maxx;i++) c[i]+=c[i-1];
        for(int i=len;i;i--) sa[c[trank[i]]--]=tsa[i];
        trank[sa[1]]=p=1;
        for(int i=2;i<=len;i++){
            if(rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+k]!=rank[sa[i-1]+k]) p++;
            trank[sa[i]]=p;
        }
        for(int i=1;i<=len;i++) rank[i]=trank[i];
    }
    for(int i=1,k=0;i<=len;i++){
        int j=sa[rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        h[rank[i]]=k;if(k>0) k--;
    }
}
int main(){
    scanf("%s",s+1);len=strlen(s+1);
    DA();
    for(int i=1;i<=len;i++) printf("%d ",sa[i]);putchar('\n');
    for(int i=2;i<=len;i++) printf("%d ",h[i]);putchar('\n');
    return 0;
}

代码掌握版

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e5+5;
char s[N];
int len,maxx,sa[N],rank[N],sum[N],tsa[N],trank[N],height[N]; 
void Radix_sort(){
    maxx=256;
    memset(sum,0,sizeof sum);//起hash数组的作用,每次用都要清零
    for(int i=1;i<=len;i++){
        rank[i]=s[i];//用ASCⅡ码表覆初值,因为ASCⅡ码表是有序的(其他离散化也可以) 
        sum[rank[i]]++;//hash转化,rank为i的后缀数++
    }
    for(int i=2;i<=maxx;i++) sum[i]+=sum[i-1];//统计总数
    for(int i=len;i;i--) sa[sum[rank[i]]--]=i;//通过总数sum[]的性质,给sa[]数组覆初值
}
void DA(){
    int p;
    Radix_sort();//基数排序 
    //sa[i]表示rank是i的后缀的第一个字母在字符串中的位置
    trank[sa[1]]=1,p=1;
    for(int i=2;i<=len;i++){
        //初始化中sa[1]的trank[]还是在第一位,由此计算剩下的sa[i]的trank[i]值
        if(rank[sa[i]]!=rank[sa[i-1]]) p++;
        trank[sa[i]]=p;//如果i项不和i-1项相同,则属于下一个排名,否则并列p名
    }
    for(int i=1;i<=len;i++) rank[i]=trank[i];//将初始化得到的rank排名复制到rank[]数组中
    //--------------------------------------------------------初始化 
    //以下开始处理其他数据,利用倍增的思想,j每次乘以2,它表示合并的单体的长度
    for(int j=1;p<len;j<<=1,maxx=p){
        //当p==len时,即没有任何两个位置的排名并列,每一个位置都有自己的排名,循环结束
        p=0;//倍增后的排名又从0开始
        for(int i=len-j+1;i<=len;i++) tsa[++p]=i;
        //从len-j+1开始,他们的第二关键字没有,故为0。所以他们在新的trank(表示第二关键字的排名)中直接就从前面排起走,即tsa[++p]直接就是i这一个位置
        for(int i=1;i<=len;i++) if(sa[i]>j) tsa[++p]=sa[i]-j;
        //sa[i]中i从1->len,所以是有序的,按照排名从小到大的;
        //sa[i]>j表示sa[i]这个位置的字符成为过sa[i]-j的第二关键字,且sa[i]-j就是目前最小的了,
        //   那么关于第二关键字排序的数组tsa[]中的下一个元素就是sa[i]-j
        //tsa[i]表示在第二关键字排序中,排名为i的子串首字母在字符串中的位置
        memset(sum,0,sizeof sum);
        for(int i=1;i<=len;i++) trank[i]=rank[tsa[i]];
        //trank[i]表示第i个位置的后缀子串的在第二关键字排序中的排名
        for(int i=1;i<=len;i++) sum[trank[i]]++;
        for(int i=2;i<=maxx;i++) sum[i]+=sum[i-1];//同样对第二关键字进行hash统计
        for(int i=len;i;i--) sa[sum[trank[i]]--]=tsa[i];
        trank[sa[1]]=1,p=1;//求新的sa[ ]数组
        for(int i=2;i<=len;i++){
            if((rank[sa[i]]!=rank[sa[i-1]])||(rank[sa[i]+j]!=rank[sa[i-1]+j])) p++;
            //此处只需要在第一关键字和第二关键字中有一个不相同,就表明这两个的新
            //排名不能并列,即要p++。
            trank[sa[i]]=p;
        }
        for(int i=1;i<=len;i++) rank[i]=trank[i];//复制数组
    }
    for(int i=1,k=0;i<=len;i++){
        int j=sa[rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        height[rank[i]]=k;if(k>0)k--;
    }
}
int main(){
    scanf("%s",s+1);len=strlen(s+1);
    DA();
    for(int i=1;i<=len;i++) printf("%d ",sa[i]);putchar('\n');
    for(int i=2;i<=len;i++) printf("%d ",height[i]);putchar('\n'); 
    return 0;
}

 


以下为广泛的不解之处和主题素材

—————————————————— 

令h[i]=height[rank[i]],则h[i]>=h[i-1]-1

对于第i个后缀,设j=sa[rank[i] –
1],约等于说j是i的按排名来的上贰个字符串,按定义来i和j的最长公共前缀正是height[rank[i]],我们前日尽管想通晓height[rank[i]]至少是多少,而小编辈要证实的正是起码是height[rank[i-1]]-1。  

证明:

先是我们不要紧设第i-1个字符串(这里以及背后指的“第?个字符串”不是按字典序排行来的,是根据首字符在字符串中的地方来的)按字典序排行来的前方的丰裕字符串是第k个字符串,注意k不必然是i-2,因为第k个字符串是按字典序排名来的i-1前边这个,并不是指在原字符串中地方在i-1前面的要命第i-2个字符串。  

 

这时,依据height[]的定义,第k个字符串和第i-1个字符串的共用前缀自然是height[rank[i-1]],未来先斟酌一下第k+1个字符串和第i个字符串的关系。  

 

第一种境况,第k个字符串和第i-1个字符串的首字符分裂,那么第k+1个字符串的排名既或然在i的前方,也说不定在i的前面,但从未涉及,因为height[rank[i-1]]便是0了啊,那么不论height[rank[i]]是有一点点都会有height[rank[i]]>=height[rank[i-1]]-1,也就是h[i]>=h[i-1]-1。  

 

其次种意况,第k个字符串和第i-1个字符串的首字符一样,那么由于第k+1个字符串正是第k个字符串去掉首字符获得的,第i个字符串也是第i-1个字符串去掉首字符得到的,那么了然第k+1个字符串要排在第i个字符串前边,要么就爆发争辩了。同一时间,第k个字符串和第i-1个字符串的最长公共前缀是height[rank[i-1]],那么自然第k+1个字符串和第i个字符串的最长公共前缀正是height[rank[i-1]]-1。  

 

到此截止,第二种境况的证实还未曾完,大家得以试想一下,对于比第i个字符串的字典序排名更靠前的那么些字符串,什么人和第i个字符串的相似度最高(这里说的相似度是指最长公共前缀的长度)?分明是排行紧邻第i个字符串的十分字符串了哟,即sa[rank[i]-1]。也便是说sa[rank[i]]和sa[rank[i]-1]的最长公共前缀至少是height[rank[i-1]]-1,那么就有height[rank[i]]>=height[rank[i-1]]-1,也即h[i]>=h[i-1]-1。  
证实完成。

4个相比基础的利用//摘抄自Yxuanw凯斯’blog

Q1:叁个串中五个串的最大公共前缀是多少? 
A1:那不正是Height吗?用rmq预处理,再O(1)查询。 
 
Q2:叁个串中可重叠的双重最长子串是多少长度? 
A2:正是求任性多个后缀的最长公共前缀,而即兴四个后缀的最长公共前缀都以Height
数组里某一段的最小值,这最长的正是Height中的最大值。 
 
Q3:三个串种不可重叠的重新最长子串是多少长度? 
A3:先二分答案转化成推断式的难点正如好管理。借使当前内需判定长度为k是不是符合供给,只需把排序后的后缀分成若干组,其中每组的后缀之间的Height
值都非常大于k,再剖断其中有未有不重复的后缀,具体正是看最大的SA值和纤维的SA值相差超不超过k,有一组超过的话k正是官方答案。 
 
Q4:三个字符串不等于的子串的个数是稍微? 
A4:种种子串一定是某些后缀的前缀,那么原难点等价于求全数后缀之间的不平等的前缀的个数。并且能够开采每三个后缀Suffix[SA[i]]的孝敬是**Len

  • SA[i] +
    1,然而有子串算重复,重复的正是Heigh[i]个与前方同样的前缀,那么减去就能够了。最终,贰个后缀Suffix[SA[i]]的孝敬正是Len
  • SA[k] + 1 – Height[k]**。 
    对于后缀数组越多的接纳这里就不详细阐释,经过考虑后各种人都会开采它的某些两样的用途,它的效果恐怕比你想象中的更加强劲!

 

三、后缀数组解题总括:

1、求单个子串的不重复子串个数。SPOJ 694、SPOJ 705.

那一个难题是叁个非凡求值难题。要认知到如此二个事实:一个字符串中的全部子串都一定是它的后缀的前缀。(那句话稍微有一点绕…)对于每三个sa[i]后缀,它的原初地点sa[i],那么它最多能获得该后缀长度个子串(n-sa[i]个),而里面有height[i]个是与前二个后缀一样的,所以它能生出的实在后缀个数就是n-sa[i]-height[i]。遍历三回具有的后缀,将它发出的后缀数加起来就是答案。

2、后缀的最长公共前缀。(记为lcp(x,y))

那是height数组的最宗旨属性之一。具体的能够参谋罗穗骞的随想。后缀i和后缀j的最长公共前缀的长度为它们在sa数组中所在排位之间的height值中的最小值。这几个描述也是有一点乱,正规的说,令x=rank[i],y=rank[j],x<y,那么lcp(i,j)=min(height[x+1],height[x+2]…height[y])。lcp(i,i)=n-sa[i]。消除那些主题材料,用RMQ的ST算法就可以(作者只会以此,或然用近些日子集体祖先那个转化的做法)。

3、最长重复子串(可重叠)

要观望,任何贰个重新子串,都必将是某四个后缀的最长公共前缀。因为,五个后缀的公物前缀,它现身在那八个后缀中,而且起始地点时分歧的,所以那几个集体前缀必然重复现身五回以上(可重叠)。而别的三个后缀的最长公共前缀为某一段height值中的最小值,所以最大为height值中的最大值(即某些lcp(sa[i],sa[i+1]))。所以就算算出height数组,然后输出最大值就能够了。

4、最长重复不重叠子串 PKU1743

其一主题材料和3的当世无双分歧在于能不可能重叠。加上不能够重叠这些范围后,直接求解比较不方便,所以大家挑选二分枚举答案,将标题转变为推断性难题。如若当时枚举的尺寸为k,那么要哪些判定是或不是存在长度为k的重新不重叠子串呢?

第一,依照height数组,将后缀分成若干组,使得每组后缀中,后缀之间的height值相当大于k。那样分组之后,轻巧看出,假如某组后缀数量超越1,那么它们中间存在贰个共用前缀,其长度为它们之间的height值的蝇头值。而笔者辈分组之后,每组后缀之间height值的小不点儿值超过等于k。所以,后缀数大于1的分组中,有望存在知足标题限制标准的长度异常的大于k的子串。只要判定满意标题限制条件创立,那么注解存在长度至少为k的官方子串。

对此主旨,限制标准是不重叠,判别的措施是,一组后缀中,初始地方最大的后缀的早先地点减去起首地方最小的后缀的发端地方>=k。满意那么些准则的话,那么那八个后缀的公家前缀不但出现四回,何况出现四遍的起头地点间距大于等于k,所以不会重叠。

深远通晓这种height分组方法以及判定重叠与否的措施,在末端的主题材料中起到重大的功效。

5、最长的产出k次的重复(可重叠)子串。 PKU3261

利用后缀数组解题时,遇到“最长”,除了非正规意况外(如难题3),一般必要二分答案,利用height值进行分组。本题的范围标准为出现k次。只需判别,有未有哪一组后缀数量非常多于k就足以了。相信有了本人前边难点的深入分析作为基础,那些应该轻巧明白。注意驾驭“十分多于k次”实际不是“等于k次”的缘由。假如通晓不了,能够找个有血有肉的事例来分析解析。

6、最长回文子串 ural1297

本条难题远非很直白的措施能够消除,但能够使用枚举的艺术。具体的正是枚举回文子串的主干四处地点i。注意要分回文子串的长短为奇数还是偶数三种景况深入分析。然后,大家要做的,是必要出以i为宗旨的回文子串最长为多少长度。利用后缀数组,能够布置出如此一种求法:求i现在的后缀与i往前的前缀的最长公共前缀。笔者那边的表明有个别标题,然则不影响掌握。

要高效地求那一个最长前缀,能够将原串反写之后接在原串前面。在采纳后缀数组的标题中,连接八个(n个)字符串时,中间要用不容许会见世在原串中,区别等的非0号的字符将它们隔绝。那样能够造成不影响后缀数组的性质。然后,难题就足以转正为求四个后缀的最长公共前缀了。具体的内部原因,留给我们温馨思考…(懒…原谅小编吧,都打那样多字了..三个多钟头了啊TOT)

7、求二个串最多由哪位串复制若干次获得 PKU2406

切切实实的难点呈报请参见PKU2406.这几个难点得以用KMP消除,并且功能比后缀数组好。

行使后缀数组直接消除本题也很劳苦(首假诺,固然二分答案,也难以化解转换而成的判别性难点。上题也是),但能够同过枚举模板串的长度k(模板串指被复制的不胜串)将标题成为八个后缀数组能够减轻的判别性难题。首先判别k能不能够被n整除,然后一旦看lcp(1,k+1)(实际在用c写程序时是lcp(0,k))是不是为n-k就足以了。

干什么这么就行了呢?那要丰硕思量到后缀的质量。当lcp(1,k+1)=n-k时,后缀k+1是后缀1(即全部字符串)的一个前缀。(因为后缀k+1的尺寸为n-k)那么,后缀1的前k个字符必然和后缀k+1的前k个字符对应一样。而后缀1的第k+1..2k个字符,又相当于后缀k+1的前k个字符,所以与后缀1的前k个字符对应同样,且和后缀k的k+1..2k又呼应一样。依次类推,只要lcp(1,k+1)=n-k,那么s[1..k]就足以经过自复制n/k次得到全方位字符串。搜索k的小不点儿值,就足以博得n/k的最大值了。

8、求多个字符串的最长公共子串。Pku2774、Ural1517

第一区分好“最长公共子串”和“最长公共子类别”。前边贰个的子串是接连的,后面一个是能够不接二连三的。

对于多个字符串的主题材料,一般情状下均将它们连起来,构造height数组。然后,最长公共子串难点也正是后缀的最长公共前缀难点。只但是,而不是全数的lcp值都能当做难题的答案。独有当七个后缀分属五个字符串时,它们的lcp值工夫作为答案。与主题材料3一模二样,本题的答案显明是有个别height值,因为lcp值是某段height值中的最小值。当区间长度为1时,lcp值等于有个别height值。所以,本题只要扫描三次后缀,寻觅后缀分属四个字符串的height值中的最大值就能够了。决断方式这里就不表达了,留给大家本人思想…

9、重复次数最多的再一次子串 SPOJ 687,Pku3693

难度比非常大的二个难题,首倘若罗穗骞的杂谈里的题解写得某些含糊不清。标题标切切实实意思能够去参谋Pku3693.

又是一题难以通过二分枚举答案解决的主题素材(因为供给的是再次次数),所以选用朴素枚举的方式。先枚举重复子串的长度k,再采用后缀数组来求长度为k的子串最多种复出现略微次。注意到一些,倘诺三个字符串它再也出现2次(这里不切磋贰回的情形,因为那是肯定的),那么它自然包涵s[0],s[k],s[2*k]…之中的邻座的多个。所以,大家可以枚举二个数i,然后推断从i*k那个岗位起的长度为k的字符串能重新出现些微次。决断方式和第88中学的相似,lcp(i*k,(i+1)*k)/k+1。然则,仅仅那样会忽略点一些特别景况,即重复子串的源点不在[i*k]职分上时的情况。这种状态应该怎么求解呢?看上面那个事例:

aabababc

当k=2,i=1时,枚举到2的职位,此时的双重子串为ba(注意第壹个人是0),lcp(2,4)=3,所以ba重复出现了2次。但事实上,开始地方为1的字符串ab出现次数越来越多,为3次。大家注意到,这种意况下,lcp(2,4)=3,3不是2的整好几倍。表达当前重复子串在终极未有多种复出现一次,而再一次出现了有些(这里是多种复出现了四个b)。假使本人那样说你未曾看懂,那么更有血有肉地:

sa[2]=bababc

sa[4]=babc

lcp=bab

至今专一到了吧,ba重复出现了两回之后,出现了三个b,而a未有出现。那么,轻松想到,能够将枚举的地点往前挪壹人,那样这么些最后的b就能够和后面包车型客车多少个a构成多少个重复子串了,而只要前挪的壹人刚刚是a,那么答案能够多1。所以,大家需须求出a=lcp(i*k,(i+1)*k)%n,然后上前挪k-a位,再用一样的艺术求其重新出现的长度。这里,令b=k-a,只须求lcp(b,b+k)>=k就足以了。实际上,lcp(b,b+k)>=k时,lcp(b,b+k)必然超越等于以前求得的lcp值,而那时候答案的尺寸只加1。未有知道的意中人细细体会下上海教室吧。

10.多个串的公共子串难点 PKU3294

率先将串连接起来,然后构造height数组,然后咋办呢?

对,二分答案再判定是还是不是行得通就行了。可行条件很直观:有一组后缀,有超过标题须求的个数个例外的字符串中的后缀存在。即,假若标题须要要出现在至少k个串中,那么就得有一组后缀,在不一样字符串中的后缀数大于等于k。

必发365游戏官方网址, 

11、出现或反转后现身全体字符串中的最长子串 PKU1226
12、不重叠地至少几回出未来富有字符串中的最长子串
故此把两题一齐说,因为它们完全一样,方法在前头的主题素材均出现过。对于三个串,连起来;反转后出现,将种种字符串反写后和原串都连起来,将反写后的串和原串看成同多少个串;求最长,二分答案后height分组;出现在颇具字符串中(反写后的也行),判别方法和10同一,k=n而已;不重叠见难题4,只不过这里对于每一个字符串都要扩充视察而已。

13、五个字符串的重复子串个数。 Pku3415

本人个人感到颇有难度的二个标题。具体的标题陈诉参看Pku3415。

14、最后的下结论

用后缀数组解题有着必然的法规可循,那是后缀的属性所调节的,具体总结如下:

1、N个字符串的难题(N>1)

格局:将它们连接起来,中间用不会产出在原串中的,互不相同的,非0号字符分隔断。

2、无界定标准下的最长公共子串(重复子串算是后缀们的最长公共前缀)

措施:height的最大值。这里的随机条件是对子串无界定标准。最五只可以是七个串的最长公共子串,才得以平昔是height的最大值。

3、特殊条件下的最长子串

办法:二分答案,再依附height数组举办分组,依照条件变成推断性难题。多个或上述的字符串的公共子串难点也亟需二分答案。设此时要注解的串长度为len,特殊条件有:

3.1、出现在k个串中

条件:属于不一致字符串的后缀个数极大于k。(在一组后缀中,下边省略)

3.2、不重叠

基准:出现在同一字符串中的后缀中,出现岗位的最大值减最小值超过等于len。

3.3、可重叠出现k次

规范:出未来同一字符串中的后缀个数大于等于k。若对于每种字符串都亟需满足,需求每一个字符串进行判定。

4、特殊计数

艺术:根据后缀的天性,和难点的渴求,通过投机的构思,看看用后缀数组能或不能够完结。一般和“子串”有关的题目,用后缀数组应该是能够减轻的。

5、重复难题

通晓一点:lcp(i,i+k)可以判别,以i为起源,长度为k的三个字符串,它向后自复制的尺寸为多少,再依赖具体难题具体深入分析,得出算法就可以。

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*
*
Website