【模板】后缀数组.cpp

// 要求T具有<运算符
template <typename T>
void sort_suffix(const T *s, int n, vector<int>& suf, vector<int>& h) {
  assert(SZ(suf) >= n && SZ(h) >= n);
  vector<int> rank(n);
  iota(all(suf), 0);
  sort(all(suf), [s](int x, int y) { return s[x] < s[y]; });
  rank[suf[0]] = 0;
  for (int i = 1; i < n; ++i) {
    rank[suf[i]] = rank[suf[i - 1]] + (s[suf[i - 1]] < s[suf[i]]);
  }
  int m = rank[suf[n - 1]] + 1;
  if (m < n) {
    //判断两个长为2*len的子串是否相等。
    //先比较第一关键字：前一半的rank，再比较第二关键字：后一半的rank。
    auto same = [n](const int *rank, int idx1, int idx2, int len) {
      return idx1 + len < n && idx2 + len < n && rank[idx1] == rank[idx2] && rank[idx1 + len] == rank[idx2 + len];
    };
    vector<int> cnt(n), suf2(n);
    int len = 1;
    do {
      // 第一步：将子串按第二关键字排序，结果存到数组suf2。
      // 这一步利用了上一轮算出的suf[]数组。
      // 这个过程可形象地理解为将子串按顺序从数组suf中拿出来放到数组suf2中。
      int p = 0;
      // 先把后一半是空串的子串放在开头，
      for (int i = n - len; i < n; i++) suf2[p++] = i;
      // 接着把后一半不是空串的子串按顺序逐个加到末尾。
      for (int i = 0; i < n; i++)
        if (suf[i] >= len)
          suf2[p++] = suf[i] - len;
      // 第二步：将n个长为2*len的子串排序。
      // 计数排序。
      // 每个子串的第一关键字是它的前一半的rank。
      for (int i = 0; i < m; i++) cnt[i] = 0;
      for (int i = 0; i < n; i++) cnt[rank[i]]++;
      for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
      for (int i = n - 1; i >= 0; i--)
        suf[--cnt[rank[suf2[i]]]] = suf2[i];
      // 第一步和第二步合起来构成一次基数排序。
      //计算rank。
      swap(rank, suf2);
      rank[suf[0]] = 0;
      for (int i = 1; i < n; i++) {
        //此时suf2存的是旧的rank。
        rank[suf[i]] = rank[suf[i - 1]] + !same(suf2.data(), suf[i - 1], suf[i], len);
      }
      m = rank[suf[n - 1]] + 1;
      len *= 2;
    } while (m < n);
  }
  //计算高度数组h。
  //对于i>=1,h[rank[i]] >= h[rank[i-1]] - 1
  for (int i = 0, lcp = 0; i < n; i++) {
    //循环不变量：每轮循环开始之前，有 h[rank[i]] >= lcp 且 lcp >= 0。
    if (rank[i] > 0) {
      int x = suf[rank[i] - 1] + lcp, y = i + lcp;
      while (x < n && y < n && s[x] == s[y]) {
        ++x, ++y, ++lcp;
      }
      h[rank[i]] = lcp;
      if (lcp > 0) --lcp;
    } else {
      h[rank[i]] = lcp;
    }
  }
}

调用 sort_suffix 之前，不需要在参数 s 的末尾补零。