后缀数组

概念讲解

什么是后缀数组？

后缀数组（Suffix Array）是将字符串的所有后缀按字典序排序后的数组。

基本概念

  • SA[i]： 排名第 i 的后缀的起始位置
  • Rank[i]： 从位置 i 开始的后缀的排名
  • LCP[i]： 排名第 i 和第 i-1 的后缀的最长公共前缀长度

实现

倍增法

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354const int N = 1000005;
int sa[N], rank[N], height[N];
int tmp[N], cnt[N];

void buildSA(string s) {
    int n = s.length();
    int m = 256;
    
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];
    }
    
    for (int k = 1; k < n; k <<= 1) {
        // 按第二关键字排序
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[rank[i + k]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) tmp[--cnt[rank[i + k]]] = i;
        
        // 按第一关键字排序
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[rank[tmp[i]]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rank[tmp[i]]]] = tmp[i];
        
        // 重新计算 rank
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + 
                         (rank[sa[i]] != rank[sa[i - 1]] || 
                          rank[sa[i] + k] != rank[sa[i - 1] + k]);
        }
        
        for (int i = 0; i < n; i++) rank[i] = tmp[i];
        if (rank[sa[n - 1]] == n - 1) break;
    }
}

void buildHeight(string s) {
    int n = s.length();
    int k = 0;
    
    for (int i = 0; i < n; i++) {
        if (rank[i] == 0) continue;
        
        int j = sa[rank[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        
        height[rank[i]] = k;
        
        if (k > 0) k--;
    }
}

应用场景

1. 最长公共子串

12345678910111213141516int longestCommonSubstring(string s1, string s2) {
    string s = s1 + "#" + s2;
    buildSA(s);
    buildHeight(s);
    
    int n = s1.length();
    int result = 0;
    
    for (int i = 1; i < s.length(); i++) {
        if ((sa[i] < n) != (sa[i - 1] < n)) {
            result = max(result, height[i]);
        }
    }
    
    return result;
}

2. 不同子串个数

12345678910111213int countDistinctSubstrings(string s) {
    buildSA(s);
    buildHeight(s);
    
    int n = s.length();
    int result = n * (n + 1) / 2;
    
    for (int i = 1; i < n; i++) {
        result -= height[i];
    }
    
    return result;
}

考点分析

初赛考查方式

  1. 选择题： 后缀数组的概念
  2. 程序阅读： 理解后缀数组
  3. 编程题： 后缀数组应用

常见题型

  • 最长公共子串
  • 不同子串个数
  • 字符串匹配

例题精讲

例题 1：最长公共子串

题目： 求两个字符串的最长公共子串。

解答：

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <iostream>
#include <cstring>
using namespace std;

const int N = 1000005;
int sa[N], rank[N], height[N];
int tmp[N], cnt[N];

void buildSA(string s) {
    int n = s.length();
    int m = 256;
    
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];
    }
    
    for (int k = 1; k < n; k <<= 1) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[rank[i + k]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) tmp[--cnt[rank[i + k]]] = i;
        
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[rank[tmp[i]]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rank[tmp[i]]]] = tmp[i];
        
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + 
                         (rank[sa[i]] != rank[sa[i - 1]] || 
                          rank[sa[i] + k] != rank[sa[i - 1] + k]);
        }
        
        for (int i = 0; i < n; i++) rank[i] = tmp[i];
        if (rank[sa[n - 1]] == n - 1) break;
    }
}

void buildHeight(string s) {
    int n = s.length();
    int k = 0;
    
    for (int i = 0; i < n; i++) {
        if (rank[i] == 0) continue;
        
        int j = sa[rank[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        
        height[rank[i]] = k;
        
        if (k > 0) k--;
    }
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    
    string s = s1 + "#" + s2;
    buildSA(s);
    buildHeight(s);
    
    int n = s1.length();
    int result = 0;
    
    for (int i = 1; i < s.length(); i++) {
        if ((sa[i] < n) != (sa[i - 1] < n)) {
            result = max(result, height[i]);
        }
    }
    
    cout << result << endl;
    
    return 0;
}

练习题

  1. 洛谷 P3809 后缀排序
查看答案

思路：后缀数组模板题。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <iostream>
#include <cstring>
using namespace std;

const int N = 1000005;
int sa[N], rank[N], tmp[N], cnt[N];

void buildSA(string s) {
    int n = s.length();
    int m = 256;
    
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];
    }
    
    for (int k = 1; k < n; k <<= 1) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[rank[i + k]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) tmp[--cnt[rank[i + k]]] = i;
        
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[rank[tmp[i]]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rank[tmp[i]]]] = tmp[i];
        
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + 
                         (rank[sa[i]] != rank[sa[i - 1]] || 
                          rank[sa[i] + k] != rank[sa[i - 1] + k]);
        }
        
        for (int i = 0; i < n; i++) rank[i] = tmp[i];
        if (rank[sa[n - 1]] == n - 1) break;
    }
}

int main() {
    string s;
    cin >> s;
    
    buildSA(s);
    
    for (int i = 0; i < s.length(); i++) {
        cout << sa[i] + 1 << " ";
    }
    cout << endl;
    
    return 0;
}
  1. 洛谷 P2408 不同子串个数
查看答案

思路：后缀数组，不同子串个数 = 总子串数 - LCP 之和。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include <iostream>
#include <cstring>
using namespace std;

const int N = 1000005;
int sa[N], rank[N], height[N], tmp[N], cnt[N];

void buildSA(string s) {
    int n = s.length();
    int m = 256;
    
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];
    }
    
    for (int k = 1; k < n; k <<= 1) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[rank[i + k]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) tmp[--cnt[rank[i + k]]] = i;
        
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[rank[tmp[i]]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rank[tmp[i]]]] = tmp[i];
        
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + 
                         (rank[sa[i]] != rank[sa[i - 1]] || 
                          rank[sa[i] + k] != rank[sa[i - 1] + k]);
        }
        
        for (int i = 0; i < n; i++) rank[i] = tmp[i];
        if (rank[sa[n - 1]] == n - 1) break;
    }
}

void buildHeight(string s) {
    int n = s.length();
    int k = 0;
    
    for (int i = 0; i < n; i++) {
        if (rank[i] == 0) continue;
        
        int j = sa[rank[i] - 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        
        height[rank[i]] = k;
        
        if (k > 0) k--;
    }
}

int main() {
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    
    buildSA(s);
    buildHeight(s);
    
    long long result = (long long)n * (n + 1) / 2;
    for (int i = 1; i < n; i++) {
        result -= height[i];
    }
    
    cout << result << endl;
    return 0;
}
  1. 洛谷 P2852 [USACO06DEC] Milk Patterns G
查看答案

思路：后缀数组 + 二分答案。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include <iostream>
#include <cstring>
using namespace std;

const int N = 20005;
int sa[N], rank[N], height[N], tmp[N], cnt[N];
int a[N];

void buildSA(int n, int m) {
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = a[i];
    }
    
    for (int k = 1; k < n; k <<= 1) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[rank[i + k]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) tmp[--cnt[rank[i + k]]] = i;
        
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[rank[tmp[i]]]++;
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rank[tmp[i]]]] = tmp[i];
        
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + 
                         (rank[sa[i]] != rank[sa[i - 1]] || 
                          rank[sa[i] + k] != rank[sa[i - 1] + k]);
        }
        
        for (int i = 0; i < n; i++) rank[i] = tmp[i];
        if (rank[sa[n - 1]] == n - 1) break;
    }
}

void buildHeight(int n) {
    int k = 0;
    
    for (int i = 0; i < n; i++) {
        if (rank[i] == 0) continue;
        
        int j = sa[rank[i] - 1];
        while (i + k < n && j + k < n && a[i + k] == a[j + k]) k++;
        
        height[rank[i]] = k;
        
        if (k > 0) k--;
    }
}

bool check(int n, int k, int mid) {
    int count = 1;
    for (int i = 1; i < n; i++) {
        if (height[i] >= mid) {
            count++;
            if (count >= k) return true;
        } else {
            count = 1;
        }
    }
    return false;
}

int main() {
    int n, k;
    cin >> n >> k;
    
    int maxVal = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        maxVal = max(maxVal, a[i]);
    }
    
    buildSA(n, maxVal + 1);
    buildHeight(n);
    
    int left = 0, right = n;
    while (left < right) {
        int mid = (left + right + 1) / 2;
        if (check(n, k, mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    
    cout << left << endl;
    return 0;
}

易错点

⚠️ 注意：

  1. 后缀数组的构造是关键
  2. LCP 数组有很多应用
  3. 后缀数组是字符串算法的高级内容
  4. 注意数组大小和边界