From 0d07389671d824396a99a0f66bb873a3eab080bd Mon Sep 17 00:00:00 2001
From: Ir1dXD <sirius.caffrey@gmail.com>
Date: Mon, 3 Dec 2018 11:44:40 +0800
Subject: [PATCH] feat: update sa

---
 docs/string/sa.md | 16 +++++++---------
 1 file changed, 7 insertions(+), 9 deletions(-)

diff --git a/docs/string/sa.md b/docs/string/sa.md
index 4c35f097..99157ec6 100644
--- a/docs/string/sa.md
+++ b/docs/string/sa.md
@@ -10,24 +10,20 @@
 
 `后缀`： 就是从 $i$ 这个位置开始到该字符串的末尾的一个子串
 
-`字符串大小`： $a$ 和 $b$ 这两个串，从头开始逐个字符按照 ASSIC 码进行比较
+`字符串大小比较`： $a$ 和 $b$ 这两个串，从头开始逐个字符按照 ASCII 码进行比较。（按照字典序比较）
 
-`后缀数组`： $sa[i]$ 代表该字符串的 $len$ 个后缀中，排名为 $i$ 的后缀是第 $sa[i]$ 个后缀
+`后缀数组`： $sa[i]$ 代表该字符串的 $len$ 个后缀中，从 $sa[i]$ 开始的后缀排在为 $i$ 个。$sa$ 数组记录的是“排第几的哪个后缀”。
 
-`名词数组`： $rank[i]$ 代表第 $i$ 个后缀排名为 $rank[i]$
+`名次数组`： $rank[i]$ 代表从 $i$ 开始的后缀排名为 $rank[i]$。$rank$ 数组记录的是“某个后缀排在第几个”。
 
 ## 一些构造方法
 
 ### 最简单的暴力
 
-把所有的后缀拆出来，然后 sort
+把所有的后缀拆出来，然后 sort。由于直接比较长度为 n 的字符串的时间复杂度为 $O(n)$，所以整体时间复杂度为 $O(n \log^2 n)$
 
-思想较为简单，可自行尝试实现
 
 ```cpp
-#include <bits/stdc++.h>
-using namespace std;
-
 int rank[123], sa[123];
 
 struct Str {
@@ -56,7 +52,7 @@ int main() {
 }
 ```
 
-### 倍增
+### 倍增法
 
 这个就是一般人写后缀数组用的方法
 
@@ -142,3 +138,5 @@ int main() {
 $y[i]$ ：假设 $y[i]=a\ ,\  y[i+1]=b$ 那么在原串中 从 $a+2^k$ 开始的 $2^k$ 个字符组成的子串 ** 小于等于 ** 从 $b+2^k$ 开始的 $2^k$ 个字符组成的子串
 
 最好理解这个代码时，每一步都结合这基数排序来考虑
+
+### DC3
-- 
2.11.0