草庐IT

后缀数组讲解及例题

Altwilio 2023-03-28 原文

时间复杂度：倍增求法，复杂度 \(O(nlogn)\)

首先把 \(s\) 的每个后缀字典序排序。
\(sa[i]:\) 排名第 \(i\) 位的是第几个后缀（起始下标）。
\(rk[i]:\) 第 \(i\) 个（起始下标为 \(i\)）的后缀的的排名。
\(height[i]:\) \(sa[i]\) 与 \(sa[i-1]\) 的最长公共前缀。

\(height\) 数组的求法：
假设所有后缀都已经排好序了，求 \(Lcp(i,j)\)
有：(\(i,j,k\) 均为排名，不作证明) $$Lcp(i,j) = Lcp(j,i)$$

\[Lcp(i,i) = len(i) \]

\[Lcp(i,j)=min(Lcp(i,k), Lcp(k,j)),i<=k<=j \]

\[height[i]=Lcp(i-1,i) \]

定义 \(h(i)=height[rk[i]]\)，即起始下标为 \(i\) 的后缀与它排名前一的后缀的最长公共前缀
有：

\[h(i)>=h(i - 1) - 1 \]

代码详细注释：

const int N = 1e6 + 10;
int n, m;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];
//c[i]每个关键字的个数
//sa[i] 排名第i位后缀编号 rank[i]编号为i的后缀的排名
//height[i] sa[i]与sa[i-1]的最长公共前缀
inline void get_sa(){
    for(int i = 1; i <= n; i ++) c[x[i] = s[i]] ++; //初始第一关键字的排名就设置为其ASCII码即可
    for(int i = 2; i <= m; i ++) c[i] += c[i - 1]; //统计前缀和，统计小于等于每个数的关键字有多少，注意只加到m
    for(int i = n; i; i --) sa[c[x[i]] --] = i; //从后往前求每个后缀的排名，数量需要减一，以第一关键字排序
    for(int k = 1; k <= n; k <<= 1){ //倍增计算sa
        int num = 0; //计算Y，排名从1开始指针指向0
        for (int i = n - k + 1; i <= n; i ++) y[++ num] = i; //后k个没有第二关键字，排名最小先分配排名
        for (int i = 1; i <= n; i ++ ){ //从小到大枚举第二关键字
            if (sa[i] <= k) continue; //前k个第一关键字不能作为某个后缀的第二关键字
            y[ ++ num] = sa[i] - k; 
            //sa为以第一关键字计算的排名，从小到大枚举排名，对应的下标其实是第 sa[i]-k 个后缀的第二关键字
        }
        for (int i = 1; i <= m; i ++ ) c[i] = 0; //清空关键字数量
        for (int i = 1; i <= n; i ++ ) c[x[i]] ++; //计算新的第一关键字每个排名有几个
        for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1]; //计算前缀和
        for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
        //y[i]以第二关键字排序，排名为i的后缀的下标 x[y[i]]上述后缀按照第一关键字的排名
        //c[x[y[i]]] 表示小于等于上述排名的数量,也就是该后缀的排名
        //sa记录上述排名对应的下标为 y[i]，从后往前枚举第二关键字的排名
        //使得第一关键字相同的后缀也可以依靠第二关键字区分
        swap(x, y);         
        //接下来要更新X数组，且要用到旧的X数组，Y数组接下里用不到，
        //则将两者交换，目的是将旧的X存到Y中，后面所有的Y实际就是旧的X
        //将当前的第一关键字和第二关键字当做下一轮的第一关键字，sa中存的就是按照双关键字排序的结果。
        x[sa[1]] = 1, num = 1; //sa[1]对于的后缀新 X的排名也为1
        for (int i = 2; i <= n; i ++ )
            //如果新排名为i的后缀和新排名为i-1的后缀的第一关键字排名相同（前一个 == ）
            //并且它们的第二关键字排名也相同（后一个 == ），那么两个后缀的新X排名相同，否则不同
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if (num == n) break; //如果已经完全区分出n个后缀了，则可以结束循环
        m = num; //更新离散化后的rank范围
    }   
}
//height[i] 表示排名为i和排名为i-1的后缀的最长公共前缀
inline void get_height(){
    for(int i = 1; i <= n; i ++) rk[sa[i]] = i; //排名为i的字符串(sa[i])排名为i
    for(int i = 1, k = 0; i <= n; i ++){
        if(rk[i] == 1) continue; //排名为1的height不用计算
        //设h[i]表示height[rk[i]]，即位于第 i个的后缀与排名在它前一个的后缀的最长公共前缀
        if(k) k --; //由于h[i]>=h[i-1]-1，所以从 k-1开始枚举
        int j = sa[rk[i] - 1]; //排名在i前一个的后缀的下标
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++; //如果相等，则最长公共前缀+1
        height[rk[i]] = k; //更新height
    }
}

例题：

\(1.\)品酒大会(\(NOI2015\))

题意：\(n\) 杯酒，每杯酒有一个标签为小写英文字母，（\(str(l, r)\) 为 \(l\) 到 \(r\) 长度为 \(r -l + 1\) 的字符串，貌似没啥用）。\(p\) 和 \(q\)“\(r\) 相似”为从 \(p\), \(q\) 开始的长度为 \(r\) 的前缀相同，每一杯酒有美味度，对于每一个 \(r\) 从 \(1\) 到 \(n-1\) 选出两杯 \(r\) 相似的酒，求 \(r\) 相似对数和 \(r\) 相似中两杯美味度相乘最大值。

思路：用后缀数组得到一个后缀排序的结果，并且 \(height\) 数组可以得到相邻两个后缀最长公共前缀的长度，并且有 *性质 ：\(i, j\) 最长前缀长度等于之间的相邻两两最长前缀最小值。对于每个固定的 \(r\) 来说，利用所有 \(height[i] < r\) 的 \(i\) 将数列分成若干段，这样所有 \(r\) 相似的后缀（酒）不可能出现在不同的段里（由于上面的 *性质），段内任意两杯酒一定 \(r\) 相似，由此可以解决第一问求个数（组合数学）。对于第二问统计最大值，三种情况可以化为两种情况（考虑正负）所以只需要在每个段里维护最大次大或最小次小就可以。现在对于固定的 \(r\) 都可以解决。现在需要解决的是所有 \(r\)。考虑用什么顺序遍历比较好处理，从大到小，最开始段多，后来段变少，合并段较容易维护所需信息。区间合并使用并查集 \(O(n)\)。
总复杂度 \(O(n) + O(nlogn)\)，并查集加后缀数组。

#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

template <class T> inline void read(T &x){
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}

template <class T> inline void print(T x){
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}

#define x first
#define y second
#define PII pair<int, int>

const int N = 3e5 + 10;
const int inf = 2e18;
int n, m; char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];
int w[N], p[N], sz[N];//并查集数组，并查集元素个数
int max1[N], max2[N], min1[N], min2[N];//最大次大最小次小
vector<int> hs[N];//记录每种值的height有哪些
PII ans[N];

//后缀数组
inline void get_sa(){
    for(int i = 1; i <= n; i ++) c[x[i] = s[i]] ++;
    for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
    for(int i = n; i; i --) sa[c[x[i]] -- ] = i;
    for(int k = 1; k <= n; k <<= 1){
        int num = 0;
        for(int i = n - k + 1; i <= n; i ++) y[++ num] = i;
        for(int i = 1; i <= n; i ++)
            if(sa[i] > k)
                y[ ++ num] = sa[i] - k;
        for(int i = 1; i <= m; i ++) c[i] = 0;
        for(int i = 1; i <= n; i ++) c[x[i]] ++ ;
        for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
        for(int i = n; i; i --) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i ++)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if(num == n) break;
        m = num;
    }
}


inline void get_height(){
    for (int i = 1; i <= n; i ++) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; i ++){
        if(rk[i] == 1) continue;
        if(k) k -- ;
        int j = sa[rk[i] - 1];
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++ ;
        height[rk[i]] = k;
    }
}

inline int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

inline int get(int x){
    return x * (x - 1ll) / 2; //即组合数C²x，x选2
}

inline PII calc(int r){
    static int cnt = 0, maxv = -inf;
    for(auto x : hs[r]){//将所有值等于r的height合并
        int a = find(x - 1), b = find(x); //合并x和x-1
        cnt -= get(sz[a]) + get(sz[b]); //减去原来两个区间的cnt
        p[a] = b; //合并 
        sz[b] += sz[a];
        cnt += get(sz[b]);//维护大小
        if(max1[a] >= max1[b]){
            max2[b] = max(max1[b], max2[b]);
            max1[b] = max1[a];
        }else if(max1[a] > max2[b]) max2[b] = max1[a];
        if(min1[a] <= min1[b]){
            min2[b] = min(min1[b], min2[a]);
            min1[b] = min1[a];
        }else if(min1[a] < min2[b]) min2[b] = min1[a];
        maxv = max(maxv, max(max1[b] * max2[b], min1[b] * min2[b]));
    }
    if(maxv == -inf) return {cnt, 0};
    return {cnt, maxv};
}

signed main(){
    read(n), m = 122;
    scanf("%s", s + 1);
    for(int i = 1; i <= n; i ++) read(w[i]);
    get_sa();
    get_height();
    for(int i = 2; i <= n; i ++) hs[height[i]].push_back(i);//把不同的height分类
    for(int i = 1; i <= n; i ++){
        p[i] = i; sz[i] = 1;
        max1[i] = min1[i] = w[sa[i]];
        max2[i] = -inf, min2[i] = inf;
    }//初始化并查集
    for(int i = n - 1; i >= 0; i --) ans[i] = calc(i);
    for(int i = 0; i < n; i ++) printf("%lld %lld\n", ans[i].x, ans[i].y);
    return 0;
}

\(2.\)生成魔咒(\(SDOI2016\))

前言：用后缀数组求字符串不同子串的数量。（静态问题）确定 \(i\) 后枚举第 \(i\) 个后缀的所有前缀。所有后缀的前缀集合就是所有子串的集合。（前置知识：P2408 不同子串个数 又水一道紫题）

\[ans = \frac {n(n+1)} 2- \sum_{i=1}^{n}height[rk[i]] \]

只需要在后缀数组板子上加上：

inline int solve(){
    int ans = 1ll * n * (n + 1) / 2;
    for(int i = 1; i <= n; i ++) ans -= height[rk[i]];
    return ans;
}

思路：来到动态，若每次往后添加一个字符，\(height\) 数组将会无法维护，将会影响前面所有的后缀，考虑将整个序列颠倒过来，边删除边维护 \(height\) 数组，动态维护，为了删除用双链表维护，对于\(i,j,k\) 若删除 \(j\) 则 \(height[k] = min(height[j],height[k])\) 可以 \(O(1)\) 实现。总的来说，将字符串翻转，将询问序列翻转，这样就是每次删除一个后缀，


#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define int long long
using namespace std;

template <class T> inline void read(T &x){
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}

template <class T> inline void print(T x){
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}

const int N = 1e5 + 10;
int n, m, s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];
int u[N], d[N], ans[N];

inline int get(int x){
    static unordered_map<int, int> hash;
    if(hash.count(x) == 0) hash[x] = ++ m;
    return hash[x];
}

inline void get_sa(){
    for(int i = 1; i <= n; i ++) c[x[i] = s[i]] ++ ;
    for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
    for(int i = n; i; i --) sa[c[x[i]] --] = i;
    for(int k = 1; k <= n; k <<= 1){
        int num = 0;
        for(int i = n - k + 1; i <= n; i ++) y[++ num] = i;
        for(int i = 1; i <= n; i ++)
            if(sa[i] > k)
                y[++ num] = sa[i] - k;
        for(int i = 1; i <= m ; i ++) c[i] = 0;
        for(int i = 1; i <= n; i ++) c[x[i]] ++ ;
        for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
        for(int i = n; i; i --) sa[c[x[y[i]]] --] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i ++)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if(num == n) break;
        m = num;
    }
}

inline void get_height(){
    for(int i = 1; i <= n; i ++) rk[sa[i]] = i;
    for(int i = 1, k = 0; i <= n; i ++){
        if(rk[i] == 1) continue;
        if(k) k -- ;
        int j = sa[rk[i] - 1];
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++;
        height[rk[i]] = k;
    } 
}

signed main(){
    read(n);
    for(int i = n; i; i --) read(s[i]), s[i] = get(s[i]);
    get_sa();
    get_height();
    int res = 0;
    for(int i = 1; i <= n; i ++){
        res += n - sa[i] + 1 - height[i];
        u[i] = i - 1, d[i] = i + 1;
    }
    d[0] = 1, u[n + 1] = n;
    for(int i = 1; i <= n; i ++){
        ans[i] = res;
        int k = rk[i], j = d[k];
        res -= n - sa[k] + 1 - height[k];
        res -= n - sa[j] + 1 - height[j];
        height[j] = min(height[j], height[k]);
        res += n - sa[j] + 1 - height[j];
        d[u[k]] = d[k], u[d[k]] = u[k];
    }
    for(int i = n; i; i --) print(ans[i]), puts("");
    return 0;
}

\(3.\)字符加密(\(JSOI2007\))

#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

template <class T> inline void read(T &x){
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}

template <class T> inline void print(T x){
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}

const int N = 1e6 + 10;
int n, m, t;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];

inline void get_sa(){
    for(int i = 1; i <= n; i ++) c[x[i] = s[i]] ++;
    for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
    for(int i = n; i; i --) sa[c[x[i]] --] = i;
    for(int k = 1; k <= n; k <<= 1){
        int num = 0;
        for(int i = n - k + 1; i <= n; i ++) y[++ num] = i;
        for (int i = 1; i <= n; i ++ )
            if (sa[i] > k)
                y[ ++ num] = sa[i] - k;

        for (int i = 1; i <= m; i ++ ) c[i] = 0;
        for (int i = 1; i <= n; i ++ ) c[x[i]] ++ ;
        for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
        for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i ++ )
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if (num == n) break;
        m = num;
    }   for(int i = 1; i <= n; i ++) c[x[i] = s[i]] ++;
}

inline void get_height(){
    for(int i = 1; i <= n; i ++) rk[sa[i]] = i;
    for(int i = 1, k = 0; i <= n; i ++){
        if(rk[i] == 1) continue;//height[1] = 0
        if(k) k --;
        int j = sa[rk[i] - 1];
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++;
        height[rk[i]] = k;
    }
}

signed main(){
    scanf("%s", s + 1);
    t = strlen(s + 1), m = 300, n = t << 1;
    for(int i = t + 1; i <= n; i ++) s[i] = s[i - t];
    get_sa();
    get_height();
    for(int i = 1; i <= n; i ++) if(sa[i] <=  t) printf("%c", s[(sa[i] + t - 1)]);
    return 0;
}
例题后缀spaninlineint算法与数据结构

有关后缀数组讲解及例题的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  3. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  4. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  5. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  6. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  7. ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2

    我正在尝试在Ruby中制作一个cli应用程序，它接受一个给定的数组，然后将其显示为一个列表，我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了，但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情，但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem，我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点？ 最佳答案 我不知道这是否是您正在寻找的，但也许您可以使用我的想法。由于我没有关于您要完成的工作

  8. ruby - 如何在 Grape 中定义哈希数组？ - 2

    我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

  9. ruby - 使用多个数组创建计数 - 2

    我正在尝试按0-9和a-z的顺序创建数字和字母列表。我有一组值value_array=['0','1','2','3','4','5','6','7','8','9','a','b'，'光盘'，'e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','','u','v','w','x','y','z']和一个组合列表的数组，按顺序，这些数字可以产生x个字符，比方说三个list_array=[]和一个当前字母和数字组合的数组(在将它插入列表数组之前我会把它变成一个字符串，]current_combo['0','0','0']

  10. ruby - 在哈希的键数组中追加元素 - 2

    查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

随机推荐