「筆記」后綴數組

過日報了

寫在前面

投了日報過了。
@ComeIntoPower 審日報的時候我正好在線，其實這篇一開始是沒有過的。

心死了，犇犇都發出去了，傷心了 10min 又來看了一眼發現過了（（（
于是順便來擴充了一下內容。

網上部分題解直接對著優化后面目全非的代碼開講。
*這太野蠻了*
這里主要參考了 OI-wiki 上的講解。

一些約定

\(\left| \sum \right|\)：字符集大小。
\(S[i:j]\)：由字符串 \(S\) 中 \(S_i\sim S_j\) 構成的子串。
\(S_1<S_2\)：字符串 \(S_1\) 的字典序 \(<S_2\)。
后綴：從某個位置 \(i\) 開始，到串末尾結束的子串，后綴 \(i\) 等價于子串 \(S[i:n]\)。每一個后綴都與一個 \(1\sim n\) 的整數一一映射。

SA

SA 的定義

字符串 \(S\) 的后綴數組定義為兩個數組 \(sa,rk\)。
\(sa\) 儲存 \(S\) 的所有后綴按字典序排序后的起始下標，滿足 \(S[sa_{i-1}:n]<S[sa_i:n]\)。
\(rk\) 儲存 \(S\) 的所有后綴的排名。

舉例：這里有一個可愛的字符串 \(S=\texttt{yuyuko}\)。
有 \(\texttt{k}<\texttt{o}<\texttt{u}<\texttt{y}\)，則它的后綴數組 \(sa = [5,6,4,2,3,1]\)，\(rk = [6,4,5,3,1,2]\)。具體地，有：

| 排名 | 1 | 2 | 3 | 4 | 5 | 6 |
|-|-|-|-|-|-|-|-|
| 下標 | \(5\) | \(6\) | \(4\) | \(2\) | \(3\) | \(1\) |
| 后綴 | \(\texttt{ko}\) | \(\texttt{o}\) | \(\texttt{uko}\) |\(\texttt{uyuko}\) | \(\texttt{yuko}\) | \(\texttt{yuyuko}\) |

不同后綴的排名必然不同（長度不等），\(rk\) 中不會有重復值出現。

倍增法構造

考慮字符串大小的從前向后的比較過程，可以先將所有長度為 \(2^k\) 的子串進行排序，通過相鄰子串合并并比較大小，求出所有長度為 \(2^{k+1}\) 的子串的大小關系。

對于 \(S[i:i+2^k-1]\) 和 \(S[j:j+2^k-1]\)，分別將它們裂開，分成兩長度為 \(2^{k-1}\) 的串。設 \(A_i = S[i:i+2^{k-1}-1]\)，\(B_i = S[i+2^{k-1}:i+2^k-1]\)。
考慮字典序排序的過程，則 \(S[i:i+2^k-1] <S[j:j+2^k-1]\) 的條件為：

\[[A_i<A_j] \operatorname{or}\ [A_i=A_j \operatorname{and} B_i<B_j] \]

考慮每一次倍增時，都使用 sort 按雙關鍵字 \(A_i\) 和 \(B_i\) 進行排序，每次倍增都進行依次排序，時間復雜度為 \(O(n\log^2 n)\)。

P3809 【模板】后綴排序
以下是一份簡單易懂的代碼。

這里定義了兩個數組：
\(sa_i\)：倍增中排名為 \(i\) 的長度為 \(2^{k-1}\) 的子串。
\(rk_i\)：倍增過程中子串 \(S[i:i+2^k-1]\) 的排名，
顯然它們互為反函數，\(sa_{rk_i}=rk_{sa_i} = i\)。

初始化 \(rk_i = S_i\)，即 \(S_i\) 的 \(\text{ASCII}\) 值。
雖然這樣不滿足值域在 \([1,n]\) 內，但體現了大小關系，可用于更新。 \(rk\) 的值之后還會更新。

//知識點：SA
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
char s[kN];
int n, m, w, sa[kN], rk[kN << 1], oldrk[kN << 1];
//rk[i]: 倍增過程中子串[i:i+2^k-1]的排名，
//sa[i] 排名為i的子串 [i:i+2^k-1]，
//它們互為反函數。
//存在越界風險，如果不寫特判，rk 和 oldrk 要開 2 倍空間。
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
bool CMP(int fir_, int sec_) {
  if (rk[fir_] != rk[sec_]) return rk[fir_] < rk[sec_];
  return rk[fir_ + w] < rk[sec_ + w];
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  m = std::max(n, 300);
  //初始化 rk 和 sa。
  //觀察下面的代碼可知，每次倍增時都會根據 rk 來更新 sa，則僅須保證 sa 數組是一個 1~n 的排列即可。
  for (int i = 1; i <= n; ++ i) sa[i] = i, rk[i] = s[i];
  //倍增過程。w 是已經推出的子串長度，數值上等于上述分析中的 2^{k-1}。
  //注意此處的 sa 數組存的并不是后綴的排名，存的是倍增過程中指定長度子串的排名。
  for (w = 1; w < n; w <<= 1) {
    std::sort(sa + 1, sa + n + 1, CMP);
    for (int i = 1; i <= n; ++ i) oldrk[i] = rk[i];
    for (int i = 1, p = 0; i <= n; ++ i) {
      if (oldrk[sa[i]] == oldrk[sa[i - 1]] && //判斷兩個子串是否相等。
          oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) { //越界風險，2倍空間
        rk[sa[i]] = p;
      } else {
        rk[sa[i]] = ++p;
      }
    }
  }
  for (int i = 1; i <= n; ++ i) printf("%d ", sa[i]);
  return 0;
}

計數排序與基數排序

優化上述算法的前置知識。

可以參考：OI-wiki 計數排序 and OI-wiki 基數排序。

計數排序是一種與桶排序類似的排序方法。
將長度為 \(n\) 的數列 \(a\) 排序后放入 \(b\) 的代碼如下，其中 \(w\) 為值域，即 \(\max\{a_i\}\)。

int a[kMaxn], b[kMaxn], cnt[kMaxw];
for (int i = 1; i <= n; ++ i) ++ cnt[a[i]];
for (int i = 1; i <= w; ++ i) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; -- i) b[cnt[a[i]] --] = a[i];

其中，在對 \(cnt\) 求前綴和后， \(cnt_i\) 為不大于 \(i\) 的數的數量，即為 \(i\) 的排名。
因此在下一步中，可以根據排名賦值。
復雜度為 \(O(n+w)\)，值域與 \(n\) 同階時復雜度比較優秀。

個人認為基數排序只是一種思想，并不算一種獨立的排序方法。
它僅僅是將 \(k\) 個排序關鍵字分開，按優先級升序依次考慮，從而實現多比較字的排序。實際每次排序還是靠其他排序方法實現。常常與計數排序相結合。

優化

請確保完全理解上述樸素實現后再閱讀下文。

發現后綴數組值域即為 \(n\)，又是多關鍵字排序，考慮基數排序。
上面已經給出一個用于比較的式子：

\[[A_i<A_j] \operatorname{or}\ [A_i=A_j \operatorname{and} B_i<B_j] \]

倍增過程中 \(A_i,B_i\) 大小關系已知，先將 \(B_i\) 作為第二關鍵字排序，再將 \(A_i\) 作為第一關鍵字排序，兩次計數排序實現即可。
單次計數排序復雜度 \(O(n + w)\)（\(w\) 為值域，顯然最大與 \(n\) 同階），總時間復雜度變為 \(O(n\log n)\)。

實現時將所有排序替換為基數排序即可。注意初始化。

//知識點：SA
/*
By:Luckyblock
I love Marisa;
But Marisa has died;
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define ll long long
const int kMaxn = 1e6 + 10;
//=============================================================
char S[kMaxn];
//rk[i]: 倍增過程中子串[i:i+2^k-1]的排名，
//sa[i] 排名為i的子串 [i:i+2^k-1]，
//它們互為反函數。
//存在越界風險，如果不寫特判，rk 和 oldrk 要開 2 倍空間。
int n, m, sa[kMaxn], rk[kMaxn << 1], oldrk[kMaxn << 1];
int id[kMaxn], cnt[kMaxn]; //用于計數排序的兩個 temp 數組
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
//=============================================================
int main() {
  scanf("%s", S + 1);
  n = strlen(S + 1);
  m = std :: max(n, 300); //值域大小
  
  //初始化 rk 和 sa
  for (int i = 1; i <= n; ++ i) ++ cnt[rk[i] = S[i]];
  for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;

  //倍增過程。w 是已經推出的子串長度，數值上等于上述分析中的 2^{k-1}。
  //注意此處的 sa 數組存的并不是后綴的排名，存的是倍增過程中指定長度子串的排名。
  for (int w = 1; w < n; w <<= 1) {
    //按照后半截 rk[i+w] 作為第二關鍵字排序。
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) id[i] = i;
    for (int i = 1; i <= n; ++ i) ++ cnt[rk[id[i] + w]]; //越界風險，2倍空間
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rk[id[i] + w]] --] = id[i];

    //按照前半截 rk[i] 作為第一關鍵字排序。
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) id[i] = sa[i];
    for (int i = 1; i <= n; ++ i) ++ cnt[rk[id[i]]];
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rk[id[i]]] --] = id[i];

    //更新 rk 數組，可以滾動數組一下，但是可讀性會比較差(
    for (int i = 1; i <= n; ++ i) oldrk[i] = rk[i];
    for (int p = 0, i = 1; i <= n; ++ i) {
      if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&  //判斷兩個子串是否相等。
          oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) { //越界風險，2倍空間
        rk[sa[i]] = p;
      } else {
        rk[sa[i]] = ++ p;
      }
    }
  }
  for (int i = 1; i <= n; ++ i) printf("%d ", sa[i]);
  return 0;
}

有一點小問題，排后半截時會枚舉到 \(id_i+w > n\) 怎么辦？
考慮實際意義，出現此情況，表示該子串后半截為空。
空串字典序最小，考慮直接把 \(rk\) 開成兩倍空間，則 \(rk_i=0\ (i>n)\) 恒成立。防止了越界，也處理了空串的字典序。

再優化

兩次計排太慢啦！觀察對后半截排序時的特殊性質：

考慮更新前的 \(sa_i\) 的含義：排名為 \(i\) 的長度為 \(2^{k-1}\) 的子串 \(S[sa_i, sa_i + 2^{k-1}]\)。
在本次排序中，\(S[sa_i, sa_i + 2^{k-1}]\) 是長度為 \(2^k\) 的子串 \(S[sa_{i}-2^{k-1}:sa_i+2^{k-1}]\) 的后半截，\(sa_i\) 的排名將作為排序的關鍵字。
\(S[sa_i, sa_i + 2^{k-1}]\) 的排名為 \(i\)，則第一次計排后 \(S[sa_{i}-2^{k-1}:sa_i+2^{k-1}]\) 的排名必為 \(i\)。考慮直接賦值，那么原來的第一次計排就可以寫成這樣：

int p = 0;
for (int i = n; i > n - w; -- i) id[++ p] = i; //后半截為空的串
for (int i = 1; i <= n; ++ i) { //根據后半截，直接推整個串的排名
  if (sa[i] > w) id[++ p] = sa[i] - w; //判斷 sa[i] > w, 保證前半截的完整
}

注意后半截為空串的情況，這樣的串排名相同且最小。

以及一些奇怪的常數優化：

減小值域。值域大小 \(m\) 與排序復雜度有關，其最小值應為 \(rk\) 的最大值，更新 \(rk\) 時更新 \(m\) 即可。
減少數組嵌套的使用，減少不連續內存訪問。在第二次計數排序時，將 \(rk_{id_i}\) 存下來。
用 cmp 函數判斷兩個子串是否相同。同樣是減少不連續內存訪問，詳見代碼。

//知識點：SA
/*
By:Luckyblock
I love Marisa;
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define ll long long
const int kMaxn = 1e6 + 10;
//=============================================================
char S[kMaxn];
int n, m, sa[kMaxn], rk[kMaxn << 1], oldrk[kMaxn << 1];
int id[kMaxn], cnt[kMaxn], rkid[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
bool cmp(int x, int y, int w) { //判斷兩個子串是否相等。
  return oldrk[x] == oldrk[y] && 
         oldrk[x + w] == oldrk[y + w]; 
}
//=============================================================
int main() {
  scanf("%s", S + 1);
  n = strlen(S + 1);
  m = std :: max(n, 300); //值域大小
  
  //初始化 sa數組
  for (int i = 1; i <= n; ++ i) ++ cnt[rk[i] = S[i]];
  for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;

  //倍增過程。 
  //此處 w = 2^{k-1}，是已經推出的子串長度。
  //注意此處的 sa 數組存的并不是后綴的排名，
  //存的是指定長度子串的排名。
  for (int p, w = 1; w < n; w <<= 1) {
    //按照后半截 rk[i+w] 作為第二關鍵字排序。
    p = 0;
    for (int i = n; i > n - w; -- i) id[++ p] = i; //后半截為空的串
    for (int i = 1; i <= n; ++ i) { //根據后半截，直接推整個串的排名
      if (sa[i] > w) id[++ p] = sa[i] - w;
    }

    //按照前半截 rk[i] 作為第一關鍵字排序。
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) ++ cnt[rkid[i] = rk[id[i]]];
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rkid[i]] --] = id[i];

    //更新 rk 數組。
    //這里可以滾動數組一下，但是可讀性會比較差（
    //卡常可以寫一下。
    std ::swap(rk, oldrk);
    m = 0; //直接更新值域 m
    for (int i = 1; i <= n; ++ i) {
      rk[sa[i]] = (m += (cmp(sa[i], sa[i - 1], w) ^ 1));
    }
  }
  for (int i = 1; i <= n; ++ i) printf("%d ", sa[i]);
  return 0;
}

線性構建

在大多數題目中，常數較小的倍增是完全夠用的。走某些特殊題目中可以使用 DC3/SA-IS 算法實現線性構建后綴數組。
具體做法可以參考：誘導排序與 SA-IS 算法與 DC3：[2009]后綴數組——處理字符串的有力工具 by. 羅穗騫。

LCP 問題

特別鳴謝：論文爺！后綴數組-許智磊

一些定義

\(\operatorname{lcp}(S,T)\) 定義為字符串 \(S\) 和 \(T\) 的最長公共前綴 (Longest common prefix)，即最大的 \(l\le \min\{\left| S\right|,\left| T\right|\}\)，滿足 \(S_i=T_i(1\le i\le l)\)。
在許多后綴數組相關問題中，都需要它的幫助。

下文以 \(\operatorname{lcp}(i,j)\) 表示后綴 \(i\)，\(j\) 的最長公共前綴，并延續上文中一些概念：\(sa_i\)：排名為 \(i\) 的后綴，\(rk_i\)：后綴 \(i\) 的排名。
并將會用 \(sa_i\) 直接代表排名為 \(i\) 的后綴，即 \(sa_i = S[sa_i:n]\)。

定義一些新的概念。
\(\operatorname{height}_i\) 表示排名為 \(i-1\) 和 \(i\) 的兩后綴的最長公共前綴。

\[\operatorname{height}_i = \operatorname{lcp}(sa_{i-1},sa_i) \]

\(h_i\) 表示后綴 \(i\) 和排名在 \(i\) 之前一位的后綴的最長公共前綴。

\[h_i=\operatorname{height}_{rk_i} = \operatorname{lcp}(sa_{rk_i-1}, sa_{rk_i})= \operatorname{lcp}(i, sa_{rk_i -1}) \]

引理：LCP Lemma

\[\forall 1\le i<j<k\le n, \,\operatorname{lcp}(sa_i,sa_k) = \min\{\operatorname{lcp}(sa_i,sa_j), \operatorname{lcp}(sa_j,sa_k)\} \]

此引理是證明其他引理的基礎。
證明，設 \(p = \min\{\operatorname{lcp}(sa_i,sa_j), \operatorname{lcp}(sa_j,sa_k)\}\)，則有：

\[\operatorname{lcp}(sa_i,sa_j)\ge p,\, \operatorname{lcp}(sa_j,sa_k)\ge p \]

則 \(sa_i[1:p] = sa_j[1:p] = sa_k[1:p]\)，可得 \(\operatorname{lcp}(sa_i,sa_k)\ge p\)。

再考慮反證法，設 \(\operatorname{lcp}(sa_i,sa_k) =q > p\)。則 \(sa_i[1:q]=sa_k[1:q]\)，有 \(sa_i[p+1]=sa_k[p+1]\)。
對 \(p\) 的取值分類討論：

\(p=\operatorname{lcp}(sa_i,sa_j) < \operatorname{lcp}(sa_j,sa_k)\)：則有 \(sa_i[p+1] < sa_j[p+1] = sa_k[p+1]\)。
\(p=\operatorname{lcp}(sa_j,sa_k) < \operatorname{lcp}(sa_i,sa_j)\)：則有 \(sa_i[p+1] = sa_j[p+1] < sa_k[p+1]\)。
\(p=\operatorname{lcp}(sa_j,sa_k) = \operatorname{lcp}(sa_i,sa_j)\)：則有 \(sa_i[p+1] < sa_j[p+1] < sa_k[p+1]\)。

\(sa_i[p+1]<sa_k[p+1]\) 恒成立，與已知矛盾，則 \(\operatorname{lcp}(sa_i,sa_k)\le p\)。
綜合上述兩個結論，得證引理成立。

引理：LCP Theorem

\[\forall 1\le i < j\le n,\, \operatorname{lcp}(sa_i,sa_j) = \min_{k=i+1}^j\{\operatorname{height_k}\} \]

由 LCP Lemma，可知顯然成立。

根據這個優美的式子，求解任意兩個后綴的 \(\operatorname{lcp}\) 變為求解 \(\operatorname{height}\) 的區間最值問題。
可通過 st 表實現 \(O(n\log n)\) 預處理，\(O(1)\) 查詢。
問題只剩下如何快速求 \(\operatorname{height}\) 了。

推論：LCP Corollary

\[\operatorname{lcp}(sa_i,sa_j) \ge \operatorname{lcp}(sa_i, sa_k)\, (i\le j<k) \]

表示排名不相鄰的兩個后綴的 \(\operatorname{lcp}\) 不超過它們之間任何相鄰元素的 \(\operatorname{lcp}\)。
證明由引理 LCP Lemma 顯然可得。
但是濤哥欽定我寫一下證明，那我就不勝惶恐地寫了（

類似 LCP Lemma，考慮反證法。設 \(\operatorname{lcp}(sa_i,sa_j)< \operatorname{lcp}(sa_i, sa_k)\)，則有下圖：

考慮字典序比較的過程。若 \(sa_i < sa_j\)，則有 \(sa_i[{\operatorname{lcp}(sa_i,sa_j)+1}] <sa_j[{\operatorname{lcp}(sa_i,sa_j) + 1}]\)。
即圖中的字符 \(x<y\)。

此時考慮比較 \(sa_j\) 與 \(sa_k\) 的字典序。由圖，顯然有 \(\operatorname{lcp}(sa_j,sa_k) = \operatorname{lcp}(sa_i,sa_j)\)。而 \(\operatorname{lcp}(sa_i,sa_k) > \operatorname{lcp}(sa_i,sa_j)\)，則 \(sa_k[{\operatorname{lcp}(sa_j,sa_k)+1}] = x\)。
又 \(x<y\)，可得 \(sa_k\) 的字典序小于 \(sa_j\)。

與已知矛盾，反證原結論成立。

引理

\[\forall 1\le i\le n,\, h_i\ge h_{i-1}-1 \]

\[h_i=\operatorname{height}_{rk_i} = \operatorname{lcp}(sa_{rk_i-1}, sa_{rk_i})= \operatorname{lcp}(i, sa_{rk_i -1}) \]

用來快速計算 \(\operatorname{height}\) 的引理，個人喜歡叫它不完全單調性。
證明考慮數學歸納。首先當 \(h_{i-1}\le 1\) 時，結論顯然成立，因為 \(h_i \ge 0\)。

當 \(h_{i-1}>1\) 時，設 \(u = i, \, v = sa_{rk_i-1}\)，有 \(h_i = \operatorname{lcp}(u,v)\)。同時，設 \(u' = i-1, \, v' = sa_{rk_{i-1}-1}\)，有 \(h_{i-1} = \operatorname{lcp}(u',v')\)。
由 \(h_{i-1} = \operatorname{lcp}(u',v')>1\)，則 \(u',v'\) 必有公共前綴。

考慮刪去 \(u',v'\) 的 第一個 字符，設其分別變成 \(x,y\)。顯然 \(\operatorname{lcp}(x,y) = h_{i-1}-1\)，且仍滿足字典序 \(y<x\)。
\(u' = i-1\)，則刪去第一個字符后，\(x\) 等于后綴 \(i\)。
則對于他們在 \(sa\) 中的排名，有 \(y<x=i=u\)。

又 \(sa\) 中，\(v\) 在 \(u\) 前一位置，則有 \(y\le v<u\)。根據 LCP Corollary，有：

\[h_i = \operatorname{lcp}(u,v)\ge \operatorname{lcp}(u,y) = \operatorname{lcp}(x,y) = h_{i-1}-1 \]

得證。

快速求 height

由定義 \(h_i = \operatorname{height}_{rk_i}\)，只需快速求出 \(h\)，便可 \(O(n)\) 地獲得 \(\operatorname{height}\)。
由引理已知 \(\forall 1\le i\le n,\, h_i\ge h_{i-1}-1\)。
\(h_i=\operatorname{lcp}(i, sa_{rk_i -1})\) 具有不完全單調性，考慮正序枚舉 \(i\) 進行遞推。

當 \(rk_i=1\) 時， \(sa_{rk_i-1}\) 不存在，特判 \(h_i=0\)。
當 \(i=1\)，暴力比較出 \(\operatorname{lcp}(i,sa_{rk_i-1})\)，比較次數 \(<n\)。
若上述情況均不滿足，由引理知，\(h_i=\operatorname{lcp}(i,sa_{rk_i-1})\ge h_{i-1}-1\)，兩后綴前 \(h_{i-1}-1\) 位相同。
可從第 \(h_{i-1}\) 位開始比較兩后綴計算出 \(h_i\)，比較次數 \(=h_i-h_{i-1}+2\)

代碼中并沒有專門開 \(h\) 數組，其中\(h_i = k\)：

void GetHeight() {
  for (int i = 1, k = 0; i <= n; ++ i) {
    if (rk[i] == 1) k = 0;
    else {
      if (k > 0) 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;
  }
}

\(k\le n\)，最多減 \(n\) 次，則最多會在比較中加 \(2n\) 次。總復雜度為 \(O(n)\) 級別。

例題

「JSOI2007」字符加密

無法簡述的題面。

斷環成鏈，把字符串復制一遍扔到后面，跑 SA 即可。
板子背誦檢查，可以練下手感。

SP705 SUBST1 - New Distinct Substrings

\(T\) 組數據，每次給定一個字符串 \(s\)，求該字符串本質不同的子串數量。
兩個子串本質不同，當且僅當兩個子串長度不等，或長度相等但有任意一位不同。
\(1\le T\le 1\le|s|\le 5\times 10^4\)。
280ms，1.46GB。

一種想法是用所有子串的個數 \(\frac{n(n+1)}{2}\) 減去重復子串的個數，顯然重復的串一定出現在某兩個后綴的公共前綴部分。

考慮加入 \(sa_i\) 后，新增的本質不同的子串的數量，顯然即 \(\operatorname{length}(sa_i) - \operatorname{length}(\operatorname{lcp}(sa_i, sa_{i-1}))\)，代表不作為之前加入的后綴的前綴的，\(sa_i\) 的前綴的數量。最終答案即：

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

SA 簡單實現即可，總復雜度 \(O(n\log n)\)。

如果想了解直觀的證明解釋可以閱讀這篇文章：「筆記」后綴樹。

//知識點：SA 
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
char s[kN];
int n, m, sa[kN], rk[kN << 1], oldrk[kN << 1], height[kN];
int id[kN], cnt[kN], rkid[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) {
    w = (w << 3) + (w << 1) + (ch ^ '0');
  }
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
bool cmp(int x_, int y_, int w_) {
  return oldrk[x_] == oldrk[y_] && 
         oldrk[x_ + w_] == oldrk[y_ + w_];
}
void GetHeight() {
  for (int i = 1, k = 0; i <= n; ++ i) {
    if (rk[i] == 1) k = 0;
    else {
      if (k > 0) -- 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;
  }
}
void SuffixSort() {
  scanf("%s", s + 1);
  m = 300;
  n = strlen(s + 1);
  
  memset(cnt, 0, sizeof (cnt));
  for (int i = 1; i <= n; ++ i) cnt[rk[i] = s[i]] ++;
  for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;
  
  for (int p, w = 1; w < n; w <<= 1) {
    p = 0;
    for (int i = n; i > n - w; -- i) id[++ p] = i;
    for (int i = 1; i <= n; ++ i) {
      if (sa[i] > w) id[++ p] = sa[i] - w;
    }
    
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) cnt[rkid[i] = rk[id[i]]] ++;
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rkid[i]] --] = id[i];
    
    m = 0;
    memcpy(oldrk, rk, sizeof (rk));
    for (int i = 1; i <= n; ++ i) {
      m += (cmp(sa[i], sa[i - 1], w) ^ 1);
      rk[sa[i]] = m;
    }
  }
  GetHeight();
}
//=============================================================
int main() {
  int T = read();
  while (T --) {
    SuffixSort();
    LL ans = 1ll * n * (n + 1) / 2ll; 
    for (int i = 1; i <= n; ++ i) ans -= height[i];
    printf("%lld\n", ans);
  }
  return 0;
}

SP1811 LCS - Longest Common Substring

給定兩字符串 \(S_1, S_2\)，求它們的最長公共子串長度。
\(|S_1|,|S_2|\le 2.5\times 10^5\)。
294ms，1.46GB。

套路地把兩個字符串連起來，答案即：

\[\max_{1\le i\le |S_1| < j\le |S_1+S_2|}\operatorname{lcp}(i,j) \]

顯然答案即為滿足 \(sa_i,sa_{i-1}\) 分屬不同字符串 的 \(\operatorname{height}_{i}\) 的最大值。
正確性非常顯然，留與讀者自證。這里給出一種證明，可以參考這里：「雙串最長公共子串」。

//知識點：SA
/*
By:Luckyblock
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctype.h>
#define ll long long
const int kMaxn = 5e5 + 10;
//=============================================================
char S[kMaxn];
int n1, n, m, ans, cnt[kMaxn], id[kMaxn], rkid[kMaxn];
int sa[kMaxn], rk[kMaxn << 1], oldrk[kMaxn << 1], height[kMaxn];
int MaxHeight[kMaxn][20], Log2[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
bool cmp(int x, int y, int w) { //判斷兩個子串是否相等。
  return oldrk[x] == oldrk[y] && 
         oldrk[x + w] == oldrk[y + w]; 
}
void GetHeight() {
  for (int i = 1, k = 0; i <= n; ++ i) {
    if (rk[i] == 1) k = 0;
    else {
      if (k > 0) 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;
  }
}
void SuffixSort() {
  m = 300;
  for (int i = 1; i <= n; ++ i) ++ cnt[rk[i] = S[i]];
  for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;
  for (int p, w = 1; w < n; w <<= 1) {
    p = 0;
    for (int i = n; i > n - w; -- i) id[++ p] = i;
    for (int i = 1; i <= n; ++ i) {
      if (sa[i] > w) id[++ p] = sa[i] - w;
    }
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) ++ cnt[(rkid[i] = rk[id[i]])];
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rkid[i]] --] = id[i];
    std ::swap(rk, oldrk);
    m = 0;
    for (int i = 1; i <= n; ++ i) {
      m += (cmp(sa[i], sa[i - 1], w) ^ 1);
      rk[sa[i]] = m;
    }
  }
  GetHeight();
}
bool Judge(int x, int y) {
  return (x <= n1 && y > n1) || (x > n1 && y < n1);
}
//=============================================================
int main() {
  scanf("%s", S + 1); n1 = strlen(S + 1);
  S[n1 + 1] = 'z' + 1;
  scanf("%s", S + n1 + 1 + 1); n = strlen(S + 1);
  SuffixSort();
  for (int i = 2; i <= n; ++ i) {
    if (Judge(sa[i - 1], sa[i])) GetMax(ans, height[i]);
  }
  printf("%d", ans);
  return 0;
}

「HAOI2016」找相同字符

給定兩字符串 \(S_1, S_2\)，求出在兩字符串中各取一個子串，使得這兩個子串相同的方案數。
兩方案不同當且僅當這兩個子串中有一個位置不同。
\(1\le |S_1|, |S_2|\le 2\times 10^5\)。
1S，256MB。

考察對 \(\operatorname{lcp}\) 單調性的理解。
\(S_1\) 后面加個終止符，\(S_2\) 串扔到 \(S_1\) 后面，跑 SA。
顯然答案即后半段的后綴，與前半段的后綴的所有 \(\operatorname{lcp}\) 之和。

考慮按字典序枚舉后半段的后綴，設當前枚舉到的后綴為 \(sa_i\)。
先 僅考慮 字典序 \(<sa_i\) 的前半段的后綴 \(sa_j\ (j<i)\) 的貢獻。其對 \(sa_i\) 的貢獻為 \(\operatorname{lcp}(sa_i, sa_j)\)。

由 \(\operatorname{lcp}\) 的單調性，對于最小的大于 \(sa_i\) 的后半段的后綴 \(sa_k(k>i)\)，有 \(\operatorname{lcp}(sa_{k}, sa_j)\le \operatorname{lcp}(sa_i,sa_j)\)，考慮貢獻的變化情況。

若 \(\operatorname{lcp}(sa_{k}, sa_j)< \operatorname{lcp}(sa_i,sa_j)\)，則 \(sa_j\) 對 \(sa_k\) 的貢獻應變為：

\[\operatorname{lcp}(sa_k, sa_j) = \min\{\operatorname{lcp}(sa_i,sa_j), \min\limits_{l=i+1}^{k}{\operatorname{height}_l}\} \]

此外，若存在 \(sa_l, l\in (i,k)\) 為 前半段的后綴 時，作出貢獻的元素增加。

考慮在枚舉后綴的過程中，用權值線段樹維護 字典序小于 \(sa_i\) 的 前半段 的后綴 \(sa_j\ (j<i)\) 的不同長度的 \(\operatorname{lcp}\) 的數量。
上述兩操作，即為區間賦值與單點插入。

再按字典序倒序枚舉后綴，計算字典序 \(>sa_i\) 的前半段的后綴的貢獻。
分析很屑，代碼有詳細注釋。

總復雜度 \(O(n\log n)\)。線段樹寫法是自己 YY 的，比較無腦，也可以單調棧簡單維護，復雜度也為 \(O(n\log n)\) 級別。
此外還有優美的廣義 SAM 寫法，可以參考：「HAOI2016」找相同字符。

//知識點：SA，線段樹
/*
By:Luckyblock 
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define ll long long
#define lson (now_<<1)
#define rson (now_<<1|1)
const int kMaxn = 4e5 + 10;
//=============================================================
char S[kMaxn];
int n1, n, m, sa[kMaxn], rk[kMaxn << 1], oldrk[kMaxn << 1], height[kMaxn];
int id[kMaxn], cnt[kMaxn], rkid[kMaxn];
ll ans, size[kMaxn << 2], sum[kMaxn << 2]; //size 維護數量，sum 維護 lcp 之和。
bool tag[kMaxn << 2];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
bool cmp(int x, int y, int w) { //判斷兩個子串是否相等。
  return oldrk[x] == oldrk[y] && 
         oldrk[x + w] == oldrk[y + w]; 
}
void GetHeight() {
  for (int i = 1, k = 0; i <= n; ++ i) {
    if (rk[i] == 1) k = 0;
    else {
      if (k > 0) 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;
  }
}
void SuffixSort() {
  m = std :: max(n, 300);
  for (int i = 1; i <= n; ++ i) ++ cnt[rk[i] = S[i]];
  for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;
  for (int p, w = 1; w < n; w <<= 1) {
    p = 0;
    for (int i = n; i > n - w; -- i) id[++ p] = i;
    for (int i = 1; i <= n; ++ i) {
      if (sa[i] > w) id[++ p] = sa[i] - w;
    }
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) ++ cnt[(rkid[i] = rk[id[i]])];
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rkid[i]] --] = id[i];
    std ::swap(rk, oldrk);
    m = 0;
    for (int i = 1; i <= n; ++ i) {
      m += (cmp(sa[i], sa[i - 1], w) ^ 1);
      rk[sa[i]] = m;
    }
  }
  GetHeight();
}
void Build(int now_, int L_, int R_) {
  size[now_] = sum[now_] = 0ll;
  tag[now_] = false;
  if (L_ == R_) return ;
  int mid = (L_ + R_) >> 1;
  Build(lson, L_, mid), Build(rson, mid + 1, R_);
}
void Pushdown(int now_) {
  tag[lson] = tag[rson] = true;
  size[lson] = size[rson] = 0;
  sum[lson] = sum[rson] = 0;
  tag[now_] = false;
}
void Pushup(int now_) {
  size[now_] = size[lson] + size[rson];
  sum[now_] = sum[lson] + sum[rson];
}
ll Delete(int now_, int L_, int R_, int ql_, int qr_) {
  if (ql_ <= L_ && R_ <= qr_) {
    ll ret = size[now_];
    tag[now_] = true;
    size[now_] = sum[now_] = 0;
    return ret;
  }
  if(tag[now_]) Pushdown(now_);
  int mid = (L_ + R_) >> 1;
  ll ret = 0ll;
  if (ql_ <= mid) ret += Delete(lson, L_, mid, ql_, qr_);
  if (qr_ > mid) ret += Delete(rson, mid + 1, R_, ql_, qr_);
  Pushup(now_);
  return ret;
}
void Insert(int now_, int L_, int R_, int pos_, ll num) {
  if (! num) return ;
  if (L_ == R_) {
    size[now_] += num;
    sum[now_] += 1ll * num * (L_ - 1ll); //注意減去偏移量。
    return ;
  }
  if (tag[now_]) Pushdown(now_);
  int mid = (L_ + R_) >> 1;
  if (pos_ <= mid) Insert(lson, L_, mid, pos_, num);
  else Insert(rson, mid + 1, R_, pos_, num);
  Pushup(now_);
}
//=============================================================
int main() {
  scanf("%s", S + 1); n1 = strlen(S + 1);
  S[n1 + 1] = 'z' + 1;
  scanf("%s", S + n1 + 2); n = strlen(S + 1);
  SuffixSort();

  //正序枚舉所有后綴，計算字典序 >sa_i 的 前半段的后綴的貢獻。
  //當枚舉到一個 后半段的后綴，僅用于更新 min(lcp)。
  //枚舉到一個 前半段的后綴，用于更新 min(lcp)，且需新插入一個后綴。
  //由于 lcp 可能為 0，線段樹維護的區間加了偏移量 1。
  for (int i = 2; i <= n; ++ i) {
    //計算 lcp > height(i) 的 前半段后綴的數量，并將他們刪除。
    ll num = Delete(1, 1, n + 1, height[i] + 1 + 1, n + 1); 
    Insert(1, 1, n + 1, height[i] + 1, num + (sa[i - 1] <= n1)); //插入被刪除的后綴 與 新后綴。注意邊界。
    if (sa[i] > n1 + 1) ans += sum[1]; //若枚舉到一個 后半段后綴，計算貢獻。 注意邊界。
  }
  Build(1, 1, n + 1); //清空線段樹
  //倒序枚舉所有后綴，計算字典序 >sa_i 的 前半段的后綴的貢獻。
  for (int i = n; i >= 2; -- i) {
    ll num = Delete(1, 1, n + 1, height[i] + 2, n + 1);
    Insert(1, 1, n + 1, height[i] + 1, num + (sa[i] <= n1)); //注意邊界
    if (sa[i - 1] > n1 + 1) ans += sum[1]; //注意邊界
  }
  printf("%lld", ans);
  return 0;
}

「AHOI2013」差異

給定一長度為 \(n\) 的字符串 \(S\)，令 \(T_i\) 表示從第 \(i\) 個字符開始的后綴，求：

\[\sum_{1\le i<j\le n}\{\operatorname{len}(T_i) +\operatorname{len}(T_j) - 2\times \operatorname{lcp} (T_i,T_j)\} \]
\(\operatorname{len}(a)\) 表示字符串 \(a\) 的長度，\(\operatorname{lcp}(a,b)\) 表示字符串 \(a,b\) 的最長公共前綴。
\(1\le n\le 5\times 10^5\)。
1S，512MB。

化下式子：

\[\begin{aligned} &\sum_{1\le i<j\le n}\{\operatorname{len}(T_i) +\operatorname{len}(T_j) - 2\times \operatorname{lcp} (T_i,T_j)\}\\ =& \sum_{1\le i<j\le n}\{(n-i+1) +(n-j+1) - 2\times \operatorname{lcp} (T_i,T_j)\}\\ =& \dfrac{(n-1)\times n \times (n+1)}{2} - 2\sum_{1\le i<j\le n}\operatorname{lcp} (T_i,T_j) \end{aligned}\]

考慮如何快速求后一半，即所有 \(\operatorname{lcp}\) 之和。
各后綴與 \(sa\) 數組的元素，一一對應，則有下列等價關系：

\[\sum_{1\le i<j\le n}\operatorname{lcp} (T_i,T_j) = \sum_{1\le i<j\le n}\operatorname{lcp}(sa_i, sa_j) \]

類似上題的套路，考慮枚舉 \(sa_j\)，用權值線段樹維護 \(sa_i (i<j)\) 的不同長度的 \(\operatorname{lcp}(sa_i, sa_j)\) 的數量。

有一引理：

\[\forall 1\le i < j\le n,\, \operatorname{lcp}(sa_i,sa_j) = \min\limits_{k=i+1}^j\{\operatorname{height_k}\} \]

模擬引理，當 \(j+1\) 時將權值線段樹中所有 \(>\operatorname{height}_{j+1}\) 的元素刪除，并添加相同個數個元素 \(\operatorname{height}_{j+1}\)。
添加一個 \(\operatorname{height}_{j+1}\)，代表新增的 \(sa_j\) 的貢獻。
貢獻求和即可，總復雜度 \(O(n\log n)\)。

線段樹太傻逼了，考慮單調數據結構。發現有下列等價關系：

\[\sum_{1\le i<j\le n}\operatorname{lcp}(sa_i, sa_j) = \sum_{1\le i<j\le n}\min_{k=i+1}^{j}\{\operatorname{height}_k\} \]

即求 \(\operatorname{height}\) 中所有子區間的區間最小值之和。
這是個經典問題，單調棧維護 \(\operatorname{height}\) 作為最小值的區間的最大左右端點，答案即 \(\sum\limits_{i=2}^{n}(i-l_i)\times (r_i-i)\times \operatorname{height}_i\)。
總復雜度 \(O(n\log n)\)。注意特判區間長度不能為 1。

線段樹代碼可以參考：這里。

//知識點：SA，單調性
/*
By:Luckyblock
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
const int kMaxn = 5e5 + 10;
//=============================================================
char S[kMaxn];
int n, m, sa[kMaxn], rk[kMaxn << 1], oldrk[kMaxn << 1], height[kMaxn];
int cnt[kMaxn], id[kMaxn], rkid[kMaxn];
int top, st[kMaxn], l[kMaxn], r[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void GetMin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
int cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && 
         oldrk[x + w] == oldrk[y + w];
}
void GetHeight() {
  for (int i = 1, k = 0; i <= n; ++ i) {
    if (rk[i] == 1) k = 0;
    else {
      if (k > 0) 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;
  }
}
void SuffixSort() {
  n = strlen(S + 1);
  m = 1010;
  for (int i = 1; i <= n; ++ i) cnt[rk[i] = S[i]] ++;
  for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
  for (int i = n; i; -- i) sa[cnt[rk[i]] --] = i;
  
  for (int p, w = 1; w < n; w <<= 1) {
    p = 0;
    for (int i = n; i > n - w; -- i) id[++ p] = i;
    for (int i = 1; i <= n; ++ i) {
      if (sa[i] > w) id[++ p] = sa[i] - w;
    }
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) cnt[rkid[i] = rk[id[i]]] ++;
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i; -- i) sa[cnt[rkid[i]] --] = id[i]; 
    
    std :: swap(rk, oldrk);
    m = 0;
    for (int i = 1; i <= n; ++ i) {
      m += (cmp(sa[i], sa[i - 1], w) ^ 1);
      rk[sa[i]] = m;
    }
  }
  GetHeight();
}
//=============================================================
int main() {
  scanf("%s", S + 1);
  SuffixSort();
  ll ans = 1ll * ((n - 1ll) * n / 2ll) * (n + 1ll) ;
  st[(top = 1)] = 1;
	for (int i = 2; i <= n; ++ i) {
		while (top && height[st[top]] > height[i]) {
		  r[st[top]] = i;
		  top --;
    }
		l[i] = st[top];
		st[++ top] = i;
	} 
  while (top) r[st[top --]] = n + 1;
  for (int i = 2; i <= n; ++ i) {
    ans -= 2ll * (i - l[i]) * (r[i] - i) * height[i]; 
  }
  printf("%lld", ans);
  return 0;
}

「TJOI / HEOI2016」字符串

給定一長度為 \(n\) 的字符串，\(m\) 個詢問。
每次詢問給定參數 \(a,b,c,d\)，求子串 \(S[a:b]\) 的所有子串，與子串 \(S[c:d]\) 的最長公共前綴的最大值。
\(1\le n,m\le 10^5, 1\le a\le b\le n, 1\le c\le d\le n\)。
2S，256MB。

對于每一個詢問，答案滿足單調性，考慮二分答案。
設 \(l\) 為當前二分到的最長的，子串 \(S[a:b]\) 的 所有子串，與子串 \(S[c:d]\) 的最長公共前綴。
分析可知，若 \(l\) 合法，那么會存在至少一個后綴 \(x\) 滿足：

開頭在 \([a:b-l+1]\) 中。
\(\operatorname{lcp}(x, c)\ge l\)。

對于第二個限制，考慮 \(\operatorname{lcp}\) 的單調性。\(\operatorname{lcp}(x,c)\) 是一個在 \(c\) 處取極值的單峰函數。
則滿足條件的 \(x\) 的取值，一定是 \(sa\) 數組上連續的一段。
套路地對 \(\operatorname{height}\) 建立 st 表，即可 \(O(1)\) 查詢 \(\operatorname{lcp}\)，于是可以通過二分排名快速得到后綴 \(x\) 排名的取值范圍，將限制二也轉化為了區間限制形式。

限制一限制了后綴的區間，限制二限制了 \(rk\) 的區間。查詢這樣的后綴的存在性，變成了一個靜態二維數點問題。
對 \(sa\) 數組建立主席樹維護即可，總復雜度 \(O(n\log^2 n)\)。

//知識點：SA，二分答案，主席樹
/*
By:Luckyblock
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctype.h>
#define ll long long
const int kMaxn = 1e5 + 10;
//=============================================================
char S[kMaxn];
int n, m, ans, cnt[kMaxn], id[kMaxn], rkid[kMaxn];
int sa[kMaxn], rk[kMaxn << 1], oldrk[kMaxn << 1], height[kMaxn];
int MaxHeight[kMaxn][20], Log2[kMaxn];;
int lson[kMaxn << 5], rson[kMaxn << 5], size[kMaxn << 5];
int node_num, root[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
bool cmp(int x, int y, int w) { //判斷兩個子串是否相等。
  return oldrk[x] == oldrk[y] && 
         oldrk[x + w] == oldrk[y + w]; 
}
void GetHeight() {
  for (int i = 1, k = 0; i <= n; ++ i) {
    if (rk[i] == 1) k = 0;
    else {
      if (k > 0) 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;
  }
}
int QueryLcp(int l_, int r_) {
  int k = Log2[r_ - l_ + 1];
  return std :: min(MaxHeight[l_][k], MaxHeight[r_ - (1 << k) + 1][k]);
}
void MakeSt() {
  for (int i = 2; i <= n; ++ i) MaxHeight[i][0] = height[i];
  for (int i = 2; i <= n; ++ i) {
    Log2[i] = Log2[i >> 1] + 1;
  }
  for (int j = 1; j < 20; ++ j) {
    for (int i = 1; i + (1 << j) - 1 <= n; ++ i) {
      MaxHeight[i][j] = std :: min(MaxHeight[i][j - 1], 
                                   MaxHeight[i + (1 << (j - 1))][j - 1]);
    }
  }
}
void SuffixSort() {
  int M = 300;
  for (int i = 1; i <= n; ++ i) ++ cnt[rk[i] = S[i]];
  for (int i = 1; i <= M; ++ i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;
  for (int p, w = 1; w < n; w <<= 1) {
    p = 0;
    for (int i = n; i > n - w; -- i) id[++ p] = i;
    for (int i = 1; i <= n; ++ i) {
      if (sa[i] > w) id[++ p] = sa[i] - w;
    }
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) ++ cnt[(rkid[i] = rk[id[i]])];
    for (int i = 1; i <= M; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rkid[i]] --] = id[i];
    std ::swap(rk, oldrk);
    M = 0;
    for (int i = 1; i <= n; ++ i) {
      M += (cmp(sa[i], sa[i - 1], w) ^ 1);
      rk[sa[i]] = M;
    }
  }
  GetHeight();
  MakeSt();
}
void Insert(int pre_, int &now_, int L_, int R_, int val_) {
  now_ = ++ node_num;
  size[now_] = size[pre_] + 1;
  lson[now_] = lson[pre_], rson[now_] = rson[pre_];
  if(L_ >= R_) return ;
  int mid = (L_ + R_) >> 1;
  if(val_ > mid) Insert(rson[pre_], rson[now_], mid + 1, R_, val_);
  else Insert(lson[pre_], lson[now_], L_, mid, val_);
}
int Query(int u_, int v_, int L_, int R_, int ql_, int qr_) {
  if (ql_ <= L_ && R_ <= qr_) return size[v_] - size[u_];
  int mid = (L_ + R_) >> 1, ret = 0;
  if (ql_ <= mid) ret += Query(lson[u_], lson[v_], L_, mid, ql_, qr_);
  if (qr_ > mid) ret += Query(rson[u_], rson[v_], mid + 1, R_, ql_, qr_);
  return ret;
}
bool Judge(int len_, int a_, int b_, int c_) {
  int l = 1, r = rk[c_], up, down;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (QueryLcp(mid + 1, rk[c_]) < len_) l = mid + 1;
    else r = mid;
  }
  up = r, l = rk[c_], r = n;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (QueryLcp(rk[c_] + 1, mid) < len_) r = mid - 1;
    else l = mid;
  }
  down = r;
  return Query(root[up - 1], root[down], 1, n, a_, b_ - len_ + 1) > 0;
}
int Solve(int a_, int b_, int c_, int d_) {
  int l = 0, r = std :: min(b_ - a_ + 1, d_ - c_ + 1);
  while (l < r) {
    int len = (l + r + 1) >> 1;
    if (Judge(len, a_, b_, c_)) l = len;
    else r = len - 1;
  }
  return r;
}
//=============================================================
int main() {
  n = read(), m = read();
  scanf("%s", S + 1);
  SuffixSort();
  for (int i = 1; i <= n; ++ i) Insert(root[i - 1], root[i], 1, n, sa[i]);
  for (int i = 1; i <= m; ++ i) {
    int a = read(), b = read(), c = read(), d = read();
    printf("%d\n", Solve(a, b, c, d));
  }
  return 0;
}

「NOI2015」品酒大會

「そして誰もいなくなるか？」

給定一字符串 \(S\)，位置 \(i\) 的屬性值為 \(a_i\)。
定義位置 \(p,q\) 為「 \(r\) 相似」，當且僅當 \(S[p:p+r-1] = S[q:q+r-1]\) 成立。
特別地，對于任意 \(1\le p,q\le n, p\not ={q}\)，\(p,q\) 都是「 \(0\) 相似」的。
求：選出兩個「 \(0\sim n-1\) 相似」的位置的 方案數，及選出兩個「 \(0\sim n-1\) 相似」的位置屬性值 乘積的最大值。
1S，256MB。

顯然，若兩個位置 \(i,j\) 是「\(r\) 相似」的，那么它們也是「\(0\sim (r-1)\) 相似」的。它們會對「\(0\sim r\) 相似」的答案做出貢獻，于是考慮倒序枚舉「\(r\) 相似」的位置計算。

發現「\(r\) 相似」問題的實質即 \(\operatorname{lcp}\) 問題，先對原串跑 SA，求得 \(\operatorname{height}\) 數組。
考慮「\(r\) 相似」的定義，則對于任意兩位置 \(i,j\)，他們最大是「\(\operatorname{lcp}(S[i:n],S[j:n])\) 相似」的。

根據引理：

\[\forall 1\le i < j\le n,\, \operatorname{lcp}(sa_i,sa_j) = \min_{k=i+1}^j\{\operatorname{height_k}\} \]

考慮按照 \(\operatorname{height}\) 將后綴排序后的后綴進行劃分。
若 \(\operatorname{height}_i\ge r\)，將 \(sa_{i-1}\) 與 \(sa_i\) 劃入一個集合，否則劃入不同的集合。這樣劃分后，對于所有大小 \(\ge 2\) 的集合，集合中所有后綴兩兩的 \(\operatorname{lcp}\ge r\)，它們都會對「\(r\) 相似」的答案做出貢獻。
將所有集合的貢獻合并，即為「\(r\) 相似」的答案。

定義上述劃分方式為「\(r\) 劃分」，考慮如何在此基礎上獲得「\(r-1\) 劃分」。
顯然，只需將 \(\operatorname{height}_i = r-1\) 的后綴 \(sa_{i-1}\) 和 \(sa_i\) 所在集合合并即可。
考慮將 \(\operatorname{height}\) 降序排序，用并查集維護集合，按上述過程依次進行合并，即可依次得到「\(n\sim 1\) 相似」的答案。

考慮如何維護集合的貢獻。

先考慮第一問，對于「\(r\) 劃分」中一個大小 \(\ge 2\) 的集合，集合中任意兩后綴的 \(\operatorname{lcp} \ge r\)，該集合的貢獻即為 \((\operatorname{size}-1)\times \operatorname{size}\)。
合并時直接將 \(\operatorname{size}\) 累加即可。

再考慮第二問，由于可能存在 \(a_i<0\)，考慮維護集合的最大值，次大值，最小值，次小值。為保證答案合法，四個值中的任意兩個都不能來自 同一個位置。
集合的貢獻為 \(\max\{max_1\times max_2, min_1 \times min_2\}\)。
合并時注意四個值的大小關系，代碼中使用了 multiset 維護。

復雜度瓶頸是倍增，總復雜度 \(O(n\log n)\) 級別，使用炫酷 DC3/SA-IS 魔術可做到 \(O(n)\) 級別的復雜度。

//知識點：SA，并查集
/*
By:Luckyblock
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <set>
#define ll long long
const int kMaxn = 3e5 + 10;
//=============================================================
char S[kMaxn];
int n, m, a[kMaxn];
int cnt[kMaxn], id[kMaxn], rkid[kMaxn];
int sa[kMaxn], rk[kMaxn << 1], oldrk[kMaxn << 1], height[kMaxn];
ll ans1[kMaxn], ans2[kMaxn];
int fa[kMaxn], size[kMaxn];
std :: multiset <int> s[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(ll &fir, ll sec) {
  if (sec > fir) fir = sec;
}
bool cmp(int x, int y, int w) { //判斷兩個子串是否相等。
  return oldrk[x] == oldrk[y] && 
         oldrk[x + w] == oldrk[y + w]; 
}
void GetHeight() {
  for (int i = 1, k = 0; i <= n; ++ i) {
    if (rk[i] == 1) k = 0;
    else {
      if (k > 0) 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;
  }
}
void SuffixSort() {
  m = 300;
  for (int i = 1; i <= n; ++ i) ++ cnt[rk[i] = S[i]];
  for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;
  for (int p, w = 1; w < n; w <<= 1) {
    p = 0;
    for (int i = n; i > n - w; -- i) id[++ p] = i;
    for (int i = 1; i <= n; ++ i) {
      if (sa[i] > w) id[++ p] = sa[i] - w;
    }
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) ++ cnt[(rkid[i] = rk[id[i]])];
    for (int i = 1; i <= m; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rkid[i]] --] = id[i];
    std ::swap(rk, oldrk);
    m = 0;
    for (int i = 1; i <= n; ++ i) {
      m += (cmp(sa[i], sa[i - 1], w) ^ 1);
      rk[sa[i]] = m;
    }
  }
  GetHeight();
}
bool Compare(int fir, int sec) {
  return height[fir] > height[sec];
}
int Find(int x) {
  return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
void Union(int x, int y, int z) {
  x = Find(x), y = Find(y);
  if (size[x] < size[y]) std :: swap(x, y);
  ans1[z] += 1ll * size[x] * size[y];
  for (std :: set <int> :: iterator it = s[y].begin(); it != s[y].end(); ++ it) {
    s[x].insert(* it);
  }
  int t[5];
  t[1] = *s[x].begin(), t[2] = *(++ s[x].begin());
  t[3] = *(-- s[x].end()), t[4] = *(-- (-- s[x].end()));
  GetMax(ans2[z], std :: max(1ll * t[1] * t[2], 1ll * t[3] * t[4]));
  fa[y] = x;
  size[x] += size[y];
  if (s[x].size() > 5) {
    s[x].clear();
    for (int i = 1; i <= 4; ++ i) s[x].insert(t[i]);
  }
}
//=============================================================
int main() {
  n = read();
  scanf("%s", S + 1);
  for (int i = 1; i <= n; ++ i) a[i] = read();
  SuffixSort();
  memset(ans2, - 63, sizeof (ans2));
  for (int i = 2; i <= n; ++ i) id[i] = i;
  for (int i = 1; i <= n; ++ i) fa[i] = i;
  for (int i = 1; i <= n; ++ i) size[i] = 1;
  std :: sort(id + 2, id + n + 1, Compare);
  for (int i = 1; i <= n; ++ i) s[i].insert(a[i]);
  for (int i = 2; i <= n; ++ i) {
    Union(sa[id[i] - 1], sa[id[i]], height[id[i]]);
  }
  for (int i = n - 1; i >= 0; -- i) {
    ans1[i] += ans1[i + 1];
    GetMax(ans2[i], ans2[i + 1]);
  }
  for (int i = 0; i < n; ++ i) {
    printf("%lld %lld\n", ans1[i], ans1[i] ? ans2[i] : 0); 
  }
  return 0;
}

「十二省聯考 2019」字符串問題

神筆出題人居然卡清空/jk
調一上午發現把昨天的 TLE 代碼的鄰接表換成 vector 就過了/jk
草草草草草

\(T\) 組數據，每次給定一字符串 \(S\)。
在 \(S\) 中存在 \(n_a\) 個 A 類子串 \((la_i, ra_i)\)，\(n_b\) 個 B 類子串 \((lb_i,rb_i)\)。且存在 \(m\) 組支配關系，支配關系 \((x,y)\) 表示第 \(x\) 個 A 類串支配第 \(y\) 個 B 類串。
要求構造一個目標串 \(T\)，滿足：

\(T\) 由若干 A 類串拼接而成。

對于分割中所有相鄰的串，后一個串存在一個被前一個串支配的前綴。

求該目標串的最大長度，若目標串可以無限長輸出 \(-1\)。
\(1\le T\le 100\)，\(n_a,n_b,|S|,m\le 2\times 10^5\)。
6S，1G。

首先建立圖論模型，從每個 A 類子串向其支配的 B 串連邊，從每個 B 串向以它為前綴的 A 串連邊。A 串節點的權值為其長度，B 串節點權值為 0。
在圖上 DP 求得最長路即為答案，若圖中存在環則無解。
第一類邊有 \(m\) 條，但第二類邊數可以達到 \(n_an_b\) 級別，考慮優化建圖。

對于某 A 串 \((la_i, ra_i)\)，它以 B 串 \((lb_j, rb_j)\) 作為一個前綴的充要條件是 \(\operatorname{lcp}(S[la_i:n],S[lb_j:n]) \ge rb_j-lb_j+1\) 且 \(ra_i - la_i + 1\ge rb_j-lb_j+1\)。
對于限制一，考慮求得 \(S\) 的 SA，對 \(\operatorname{height}\) 建立 ST 表，可在 \(sa\) 上二分求得滿足 \(\operatorname{lcp}\ge rb_j-lb_j+1\) 的區間的左右邊界，滿足條件的 A 串一定都在這段區間內。第二類邊轉化為區間連邊問題。
此時不考慮限制二直接線段樹優化建圖，可以拿到 80 分的好成績。

限制二實際上限定了 B 連邊的對象的長度。
考慮將所有 A，B 串按長度遞減排序，按長度遞減枚舉 A 串并依次加入可持久化線段樹。
對于每一個 B 串，先找到使得 A 串長度大于其長度的最晚的歷史版本，此時線段樹上的所有 A 串長度都大于其長度，再向這棵線段樹上的節點連邊。

時間復雜度 \(O((|S| + n_a + n_b)\log n)\)，空間復雜度 \(O(m + (|S| + n_a + n_b)\log n)\)，不需要刻意卡常就能穩過。

看見上面輕描淡寫的是不是覺得這題太傻逼了？以下是菜雞 Lb 在代碼實現上的小問題。

邊數在極限數據下可以達到 \(10^7\) 級別，不注意空間大小和清空時的實現會被卡到 60。這個時空限制顯然就是給選手亂搞的，數組往大了開就行。

在線段樹優化建圖中，實點會在建樹操作中就與虛點連好邊。本題的實點是代表 A，B 串的節點，在本題的可持久化線段樹優化中，實點與虛點的連邊發生在動態開點的插入過程中。
在新建節點時，需要將該節點連向上一個版本中對應位置的節點。
對于 A 串 \((la_i, ra_i)\)，它應該被插入到線段樹中 \(rk_{la_i}\) 的位置，即葉節點 \(rk_{la_i}\) 與該實點相連。

\(\operatorname{height}_1\) 沒有意義。

注意二分時的初始值。

long long

函數傳參順序是通過棧傳遞的，因此是從右向左的。

//知識點：SA，可持久化線段樹，優化建圖，DAGDP
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
struct Str {
  int l, r, lth, id;
} subs[kN << 1];
int node_num, n, na, nb, m, into[kN <<5];
int e_num, head[kN << 5], v[50 * kN], ne[50 * kN];
LL val[kN << 5], f[kN << 5];
char s[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) {
    w = (w << 3) + (w << 1) + (ch ^ '0');
  }
  return f * w;
}
void Chkmax(LL &fir_, LL sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
bool cmp(Str fir_, Str sec_) {
  if (fir_.lth != sec_.lth) return fir_.lth > sec_.lth;
  return fir_.id < sec_.id;
}
void Add(int u_, int v_) {
  v[++ e_num] = v_, ne[e_num] = head[u_], head[u_] = e_num;
  into[v_] ++;
}
namespace ST {
  int Minn[kN][21], Log2[kN];
  void MakeST(int *a_) {
    for (int i = 1; i <= n; ++ i) Minn[i][0] = a_[i];
    for (int i = 2; i <= n; ++ i) Log2[i] = Log2[i >> 1] + 1;
    for (int j = 1; j <= 20; ++ j) {
      for (int i = 1; i + (1 << j) - 1 <= n; ++ i) { //
        Minn[i][j] = std::min(Minn[i][j - 1], Minn[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  int Query(int l_, int r_) {
    int k = Log2[r_ - l_ + 1];
    return std::min(Minn[l_][k], Minn[r_ - (1 << k) + 1][k]);
  }
}
namespace SA {
  int sa[kN], rk[kN << 1];
  int oldrk[kN << 1], cnt[kN], id[kN];
  int height[kN];
  void SuffixSort() {
    int rknum = std::max(n, 300);
    memset(cnt, 0, sizeof (cnt));
    for (int i = 1; i <= n; ++ i) cnt[rk[i] = s[i]] ++;
    for (int i = 1; i <= rknum; ++ i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; -- i) sa[cnt[rk[i]] --] = i;
    
    for (int w = 1, p; w < n; w <<= 1) {
      p = 0;
      for (int i = n; i > n - w; -- i) id[++ p] = i;
      for (int i = 1; i <= n; ++ i) {
        if (sa[i] > w) id[++ p] = sa[i] - w;
      }
      
      memset(cnt, 0, sizeof (cnt));
      for (int i = 1; i <= n; ++ i) ++ cnt[rk[id[i]]];
      for (int i = 1; i <= rknum; ++ i) cnt[i] += cnt[i - 1];
      for (int i = n; i >= 1; -- i) sa[cnt[rk[id[i]]] --] = id[i];
      
      for (int i = 1; i <= n; ++ i) oldrk[i] = rk[i];
      rknum = 0;
      for (int i = 1; i <= n; ++ i) {
        rknum += (oldrk[sa[i]] == oldrk[sa[i - 1]] && 
                  oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) ^ 1;
        rk[sa[i]] = rknum;
      }
    }
  }
  void GetHeight() {
    for (int i = 1, k = 0; i <= n; ++ i) {
      if (rk[i] == 1) {
        k = 0;
      } else {
        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;
    }
  }
  int Lcp(int x_, int y_) {
    if (x_ > y_) std::swap(x_, y_);
    return ST::Query(x_ + 1, y_);
  }
  void Init() {
    SuffixSort();
    GetHeight();
    ST::MakeST(SA::height);
  }
}
namespace Hjt {
  #define ls lson[now_]
  #define rs rson[now_]
  #define mid ((L_+R_)>>1)
  int root[kN], lson[kN << 5], rson[kN << 5];
  void Insert(int &now_, int pre_, int L_, int R_, int pos_, int id_) {
    now_ = ++ node_num;
    ls = lson[pre_], rs = rson[pre_];
    if (pre_) Add(now_, pre_);
    if (L_ == R_) {
      Add(now_, id_);
      return ;
    }
    if (pos_ <= mid) {
      Insert(ls, lson[pre_], L_, mid, pos_, id_);
      Add(now_, ls);
    } else {
      Insert(rs, rson[pre_], mid + 1, R_, pos_, id_);
      Add(now_, rs);
    }
  }
  void AddEdge(int now_, int L_, int R_, int l_, int r_, int id_) {
    if (! now_) return ;
    if (l_ <= L_ && R_ <= r_) {
      Add(id_, now_);
      return ;
    }
    if (l_ <= mid) AddEdge(ls, L_, mid, l_, r_, id_);
    if (r_ > mid) AddEdge(rs, mid + 1, R_, l_, r_, id_);
  }
  #undef ls
  #undef rs
  #undef mid
}
void Init() {
  e_num = 0;
  for (int i = 0; i <= node_num; ++ i) {
    head[i] = val[i] = into[i] = f[i] = 0;
  }
  
  scanf("%s", s + 1);
  n = strlen(s + 1);
  SA::Init();
  na = read();
  for (int i = 1; i <= na; ++ i) {
    int l_ = read(), r_ = read();
    subs[i] = (Str) {l_, r_, r_ - l_ + 1, i};
    val[i] = subs[i].lth;
  }
  nb = read();
  for (int i = 1; i <= nb; ++ i) {
    int l_ = read(), r_ = read();
    subs[na + i] = (Str) {l_, r_, r_ - l_ + 1, na + i};
  }
  m = read();
  for (int i = 1; i <= m; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_ + na); //Add(read(), read()+na) 會倒著讀
  }
  node_num = na + nb;
}
bool Check(int x_, int y_, int lth_) {
  return SA::Lcp(x_, y_) >= lth_;
}
void AddEdgeB(int id_, int now_) {
  int pos = SA::rk[subs[id_].l], l_ = pos, r_ = pos; //l_，r_ 初始值
  for (int l = 1, r = pos - 1; l <= r; ) {
    int mid = (l + r) >> 1;
    if (Check(mid, pos, subs[id_].lth)) {
      r = mid - 1;
      l_ = mid;
    } else {
      l = mid + 1;
    }
  }
  for (int l = pos + 1, r = n; l <= r; ) {
    int mid = (l + r) >> 1;
    if (Check(pos, mid, subs[id_].lth)) {
      l = mid + 1;
      r_ = mid;
    } else {
      r = mid - 1; 
    }
  }
  Hjt::AddEdge(Hjt::root[now_], 1, n, l_, r_, subs[id_].id);
}
void Build() {
  node_num = na + nb;
  std::sort(subs + 1, subs + na + nb + 1, cmp);
  for (int now = 0, i = 1; i <= na + nb; ++ i) {
    if (subs[i].id > na) {
      AddEdgeB(i, now);
      continue;
    }
    ++ now;
    Hjt::Insert(Hjt::root[now], Hjt::root[now - 1], 1, n, SA::rk[subs[i].l], 
                subs[i].id);
  }
}
void TopSort() {
  std::queue <int> q;
  for (int i = 1; i <= node_num; ++ i) {
    if (!into[i]) {
      f[i] = val[i];
      q.push(i);
    }
  }
  while (! q.empty()) {
    int u_ = q.front(); q.pop();
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      Chkmax(f[v_], f[u_] + val[v_]);
      -- into[v_];
      if (!into[v_]) q.push(v_);
    }
  }
  LL ans = 0;
  for (int i = 1; i <= node_num; ++ i) {
    Chkmax(ans, f[i]);
    if (into[i]) {
      printf("-1\n");
      return ;
    }
  }
  printf("%lld\n", ans);
}
//=============================================================
int main() {
  int T = read();
  while (T --) {
    Init();
    Build();
    TopSort();
  }
  return 0;
}

與后綴樹的聯系

后綴樹相關介紹可以參考：「筆記」后綴樹。

SA 可以看作由后綴樹的所有葉結點按字典序排列得到的數組。
SA 的 \(\operatorname{height}\) 數組可以看做后綴樹中相鄰兩關鍵點的 \(\operatorname{lca}\)，從這個角度上可以直觀地理解 SA 的許多性質。

同時，這也證明了后綴樹的適用范圍一定比 SA 大。
奈何 SA 配合 \(\operatorname{height}\) 可以實現大部分后綴樹的功能，又好寫，時間上與后綴樹又幾乎相同，空間又小，所以我喜歡 SA（

做題的時候可以先直觀地從后綴樹的角度出發思考，再用 SA 進行實現。
可以避免抽象的思考過程，比較適合我這樣的無腦選手（

后綴數組結合虛樹的思想可以用于構建后綴樹，詳見這篇博客：利用后綴數組構造后綴樹_AZUI

寫在最后

參考資料：

OI-wiki SA
后綴數組詳解 - 自為風月馬前卒
 「后綴排序SA」學習筆記 - Rainy7
后綴數組-許智磊
 后綴數組學習筆記 _ Menci's Blog
利用后綴數組構造后綴樹_AZUI
P5284 [十二省聯考2019]字符串問題 - xht37 的洛谷博客

posted @ 2020-12-31 15:31 Luckyblock 閱讀(526) 評論(3) 收藏舉報

刷新頁面返回頂部

Luckyblock

身與華落，心將香飛

「筆記」后綴數組

寫在前面

一些約定

SA

SA 的定義

倍增法構造

計數排序與基數排序

優化

再優化

線性構建

LCP 問題

一些定義

引理：LCP Lemma

引理：LCP Theorem

推論：LCP Corollary

引理

快速求 height

例題

「JSOI2007」字符加密

SP705 SUBST1 - New Distinct Substrings

SP1811 LCS - Longest Common Substring

「HAOI2016」找相同字符

「AHOI2013」差異

「TJOI / HEOI2016」字符串

「NOI2015」品酒大會

「十二省聯考 2019」字符串問題

與后綴樹的聯系

寫在最后

公告

身與華落，心將香飛

寫在前面

一些約定

SA

SA 的定義

倍增法構造

計數排序 與 基數排序

優化

再優化

線性構建

LCP 問題

一些定義

引理：LCP Lemma

引理：LCP Theorem

推論：LCP Corollary

引理

快速求 height

例題

與后綴樹的聯系

寫在最后

公告

計數排序與基數排序