From 37ba8387564b9b8ee4d877480918f3922875f815 Mon Sep 17 00:00:00 2001
From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com>
Date: Tue, 10 Sep 2019 20:32:47 -0400
Subject: [PATCH] style: format markdown files with remark-lint

---
 docs/string/automaton.md   | 40 +++++++++++++++++++++-------------------
 docs/string/general-sam.md |  1 +
 docs/string/hash.md        | 38 +++++++++++++++++---------------------
 docs/string/index.md       | 26 +++++++++++++-------------
 docs/string/match.md       | 16 ++++++++--------
 5 files changed, 60 insertions(+), 61 deletions(-)

diff --git a/docs/string/automaton.md b/docs/string/automaton.md
index 69d41e37..78862935 100644
--- a/docs/string/automaton.md
+++ b/docs/string/automaton.md
@@ -2,21 +2,21 @@
 
 ## 定义
 
-一个**确定有限状态自动机（DFA）**由以下五部分构成：
+一个 **确定有限状态自动机（DFA）** 由以下五部分构成：
 
-1. **字符集**（$\Sigma$），该自动机只能输入这些字符。
-2. **状态集合**（$Q$）。如果把一个 DFA 看成一张有向无环图（DAG），那么 DFA 中的状态就相当于图上的顶点。
-3. **起始状态**（$start$），$start\in Q$，是一个特殊的状态。起始状态一般用 $s$ 表示，为了避免混淆，本文中使用 $start$。
-4. **接受状态集合**（$F$），$F\subseteq Q$，是一堆特殊的状态。
-5. **转移函数**（$\delta$），$\delta$ 是一个接受两个参数返回一个值的函数，其中第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。如果把一个 DFA 看成一张有向无环图（DAG），那么 DFA 中的转移函数就相当于顶点间的边，而每条边上都有一个字符。
+1.   **字符集** （ $\Sigma$ ），该自动机只能输入这些字符。
+2.   **状态集合** （ $Q$ ）。如果把一个 DFA 看成一张有向无环图（DAG），那么 DFA 中的状态就相当于图上的顶点。
+3.   **起始状态** （ $start$ ）， $start\in Q$ ，是一个特殊的状态。起始状态一般用 $s$ 表示，为了避免混淆，本文中使用 $start$ 。
+4.   **接受状态集合** （ $F$ ）， $F\subseteq Q$ ，是一堆特殊的状态。
+5.   **转移函数** （ $\delta$ ）， $\delta$ 是一个接受两个参数返回一个值的函数，其中第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。如果把一个 DFA 看成一张有向无环图（DAG），那么 DFA 中的转移函数就相当于顶点间的边，而每条边上都有一个字符。
 
-DFA 的作用就是识别字符串，一个自动机 $A$，若它能识别（接受）字符串 $S$，那么 $A(S)=True$，否则 $A(S)=False$。
+DFA 的作用就是识别字符串，一个自动机 $A$ ，若它能识别（接受）字符串 $S$ ，那么 $A(S)=True$ ，否则 $A(S)=False$ 。
 
 当一个 DFA 读入一个字符串时，从初始状态起按照转移函数一个一个字符地转移。如果读入完一个字符串的所有字符后位于一个接受状态，那么我们称这个 DFA **接受** 这个字符串，反之我们称这个 DFA **不接受** 这个字符串。
 
-如果一个状态 $v$ 没有字符 $c$ 的转移，那么我们令 $\delta(v,c)=null$，而 $null$ 只能转移到 $null$，且 $null$ 不属于接受状态集合。无法转移到任何一个接受状态的状态都可以视作 $null$，或者说，$null$ 代指所有无法转移到任何一个接受状态的状态。
+如果一个状态 $v$ 没有字符 $c$ 的转移，那么我们令 $\delta(v,c)=null$ ，而 $null$ 只能转移到 $null$ ，且 $null$ 不属于接受状态集合。无法转移到任何一个接受状态的状态都可以视作 $null$ ，或者说， $null$ 代指所有无法转移到任何一个接受状态的状态。
 
-我们扩展定义转移函数 $\delta$，令其第二个参数可以接收一个字符串：$\delta(v,s)=\delta(\delta(v,s[0]),s[1..|s|-1])$，这个扩展后的转移函数就可以表示从一个状态起接收一个字符串后转移到的状态。那么，$A(s)=[\delta(start,s)\in F]$。
+我们扩展定义转移函数 $\delta$ ，令其第二个参数可以接收一个字符串： $\delta(v,s)=\delta(\delta(v,s[0]),s[1..|s|-1])$ ，这个扩展后的转移函数就可以表示从一个状态起接收一个字符串后转移到的状态。那么， $A(s)=[\delta(start,s)\in F]$ 。
 
 如，一个接受且仅接受字符串 $a,ab,aac$ 的 DFA：
 
@@ -26,15 +26,16 @@ DFA 的作用就是识别字符串，一个自动机 $A$，若它能识别（接
 
 ### 字典树
 
-[字典树](./trie.md) 是大部分 OIer 接触到的第一个自动机，接受且仅接受指定的字符串集合中的元素。
+ [字典树](./trie.md) 是大部分 OIer 接触到的第一个自动机，接受且仅接受指定的字符串集合中的元素。
 
 转移函数就是 Trie 上的边，接受状态是将每个字符串插入到 Trie 时到达的那个状态。
 
 ### KMP 自动机
 
-[KMP 算法](./kmp.md) 可以视作自动机，基于字符串 $s$ 的 KMP 自动机接受且仅接受以 $s$ 为后缀的字符串，其接受状态为 $|s|$。
+ [KMP 算法](./kmp.md) 可以视作自动机，基于字符串 $s$ 的 KMP 自动机接受且仅接受以 $s$ 为后缀的字符串，其接受状态为 $|s|$ 。
 
 转移函数：
+
 $$
 \delta(i, c)=
 \begin{cases}
@@ -42,33 +43,34 @@ i+1&s[i+1]=c\\
 \delta(\pi(i),c)&s[i+1]\ne c
 \end{cases}
 $$
-（需要特别定义 $\forall c\in\Sigma,\delta(\pi(1),c)=1$）
+
+（需要特别定义 $\forall c\in\Sigma,\delta(\pi(1),c)=1$ ）
 
 ### AC 自动机
 
-[AC 自动机](./ac-automaton.md) 接受且仅接受以指定的字符串集合中的某个元素为后缀的字符串。也就是 Trie + KMP。
+ [AC 自动机](./ac-automaton.md) 接受且仅接受以指定的字符串集合中的某个元素为后缀的字符串。也就是 Trie + KMP。
 
 ### 后缀自动机
 
-[后缀自动机](./sam.md) 接受且仅接受指定字符串的后缀。
+ [后缀自动机](./sam.md) 接受且仅接受指定字符串的后缀。
 
 ### 广义后缀自动机
 
-[广义后缀自动机](./general-sam.md) 接受且仅接受指定的字符串集合中的某个元素的后缀。也就是 Trie + SAM。
+ [广义后缀自动机](./general-sam.md) 接受且仅接受指定的字符串集合中的某个元素的后缀。也就是 Trie + SAM。
 
 广义 SAM 与 SAM 的关系就是 AC 自动机与 KMP 自动机的关系。
 
 ### 回文自动机
 
-[回文自动机](./pam.md) 比较特殊，它不能非常方便地定义为自动机。
+ [回文自动机](./pam.md) 比较特殊，它不能非常方便地定义为自动机。
 
-如果需要定义的话，它接受且仅接受某个字符串的所有回文子串的 **中心及右半部分**。
+如果需要定义的话，它接受且仅接受某个字符串的所有回文子串的 **中心及右半部分** 。
 
 “中心及右边部分”在奇回文串中就是字面意思，在偶回文串中定义为一个特殊字符加上右边部分。这个定义看起来很奇怪，但它能让 PAM 真正成为一个自动机，而不仅是两棵树。
 
 ### 序列自动机
 
-[序列自动机](./seq-automaton.md) 接受且仅接受指定字符串的子序列。
+ [序列自动机](./seq-automaton.md) 接受且仅接受指定字符串的子序列。
 
 ## 后缀链接
 
@@ -84,4 +86,4 @@ $$
 
 在计算复杂性领域中，自动机是一个经典的模型。并且，自动机与正则语言有着密不可分的关系。
 
-如果对相关内容感兴趣的话，推荐阅读博客 [计算复杂性(1) Warming Up: 自动机模型](https://lingeros-tot.github.io/2019/03/05/Warming-Up-自动机模型/)。
\ No newline at end of file
+如果对相关内容感兴趣的话，推荐阅读博客 [计算复杂性（1) Warming Up: 自动机模型](https://lingeros-tot.github.io/2019/03/05/Warming-Up-自动机模型/) 。
diff --git a/docs/string/general-sam.md b/docs/string/general-sam.md
index e69de29b..8b137891 100644
--- a/docs/string/general-sam.md
+++ b/docs/string/general-sam.md
@@ -0,0 +1 @@
+
diff --git a/docs/string/hash.md b/docs/string/hash.md
index 3799e596..c7be51d4 100644
--- a/docs/string/hash.md
+++ b/docs/string/hash.md
@@ -4,11 +4,11 @@ Hash 的核心思想在于，将输入映射到一个值域较小、可以方便
 
 !!! warning
     这里的“值域较小”在不同情况下意义不同。
-    
+
     在 [哈希表](../ds/hash.md) 中，值域需要小到能够接受线性的空间与时间复杂度。
-    
-    在字符串哈希中，值域需要小到能够快速比较（$10^9$、$10^{18}$ 都是可以快速比较的）。
-    
+
+    在字符串哈希中，值域需要小到能够快速比较（ $10^9$ 、 $10^{18}$ 都是可以快速比较的）。
+
     同时，为了降低哈希冲突率，值域也不能太小。
 
 我们定义一个把字符串映射到整数的函数 $f$ ，这个 $f$ 称为是 Hash 函数。
@@ -41,19 +41,16 @@ const int B = 233;
 
 typedef long long ll;
 
-int get_hash(const string& s)
-{
-    int res = 0;
-    for (int i = 0; i < s.size(); ++i)
-    {
-        res = (ll) (res * B + s[i]) % mod;
-	}
-    return res;
+int get_hash(const string& s) {
+  int res = 0;
+  for (int i = 0; i < s.size(); ++i) {
+    res = (ll)(res * B + s[i]) % mod;
+  }
+  return res;
 }
 
-void cmp(const string& s, const string& t)
-{
-    return get_hash(s) == get_hash(t);
+void cmp(const string& s, const string& t) {
+  return get_hash(s) == get_hash(t);
 }
 ```
 
@@ -61,7 +58,7 @@ void cmp(const string& s, const string& t)
 
 ### 错误率
 
-由于 $n$ 远大于 $m$ ，要进行约 $n$ 次比较，每次错误率 $\frac1{M}$ ，那么总错误率是 $1-(1-1/M)^n$ 。在随机数据下，若 $M=10^9 + 7$, $n=10^6$，错误率约为 $\frac 1{1000}$，并不是能够完全忽略不计的。
+由于 $n$ 远大于 $m$ ，要进行约 $n$ 次比较，每次错误率 $\frac1{M}$ ，那么总错误率是 $1-(1-1/M)^n$ 。在随机数据下，若 $M=10^9 + 7$ , $n=10^6$ ，错误率约为 $\frac 1{1000}$ ，并不是能够完全忽略不计的。
 
 所以，进行字符串哈希时，经常会对两个大质数分别取模，这样的话哈希函数的值域就能扩大到两者之积，错误率就非常小了。
 
@@ -71,7 +68,7 @@ void cmp(const string& s, const string& t)
 
 一般采取的方法是对整个字符串先预处理出每个前缀的哈希值，将哈希值看成一个 $b$ 进制的数对 $M$ 取模的结果，这样的话每次就能快速求出子串的哈希了：
 
-令 $f_i(s)$ 表示 $f(s[1..i])$，那么 $f(s[l..r])=\frac{f_r[s]-f_{l-1}(s)}{b^{l-1}}$，其中 $\frac{1}{b^{l-1}}$ 也可以预处理出来，用 [乘法逆元](../math/inverse.md) 或者是在比较哈希值时等式两边同时乘上 $b$ 的若干次方化为整式均可。
+令 $f_i(s)$ 表示 $f(s[1..i])$ ，那么 $f(s[l..r])=\frac{f_r[s]-f_{l-1}(s)}{b^{l-1}}$ ，其中 $\frac{1}{b^{l-1}}$ 也可以预处理出来，用 [乘法逆元](../math/inverse.md) 或者是在比较哈希值时等式两边同时乘上 $b$ 的若干次方化为整式均可。
 
 这样的话，就可以在 $O(\text{串长})$ 的预处理后每次 $O(1)$ 地计算子串的哈希值了。
 
@@ -83,7 +80,7 @@ void cmp(const string& s, const string& t)
 
 ### 最长回文子串
 
-二分答案，判断是否可行时枚举回文中心（对称轴），哈希判断两侧是否相等。需要分别预处理正着和倒着的哈希值。时间复杂度 $O(n\log n)$。
+二分答案，判断是否可行时枚举回文中心（对称轴），哈希判断两侧是否相等。需要分别预处理正着和倒着的哈希值。时间复杂度 $O(n\log n)$ 。
 
 这个问题可以使用 [manacher 算法](./manacher.md) 在 $O(n)$ 的时间内解决。
 
@@ -91,8 +88,7 @@ void cmp(const string& s, const string& t)
 
 ???+note "[CF1200E Compress Words](http://codeforces.com/contest/1200/problem/E)"
     题目大意：给你若干个字符串，答案串初始为空。第 $i$ 步将第 $i$ 个字符串加到答案串的后面，但是尽量地去掉重复部分（即去掉一个最长的、是原答案串的后缀、也是第 $i$ 个串的前缀的字符串），求最后得到的字符串。
-    
 
     每次需要求最长的、是原答案串的后缀、也是第 $i$ 个串的前缀的字符串。枚举这个串的长度，哈希比较即可。
-    
-    当然，这道题也可以使用 [KMP 算法](./kmp.md) 解决。
\ No newline at end of file
+
+    当然，这道题也可以使用 [KMP 算法](./kmp.md) 解决。
diff --git a/docs/string/index.md b/docs/string/index.md
index ca20b824..49df89d7 100644
--- a/docs/string/index.md
+++ b/docs/string/index.md
@@ -2,42 +2,42 @@
 
 ### 字符集
 
-一个**字符集** $Σ$ 是一个建立了全序关系的集合，也就是说，$Σ$ 中的任意两个不同的元素 $α$ 和 $β$ 都可以比较大小，要么 $α<β$，要么 $β<α$（也就是$α>β$）。字符集 $Σ$ 中的元素称为字符。
+一个 **字符集**  $Σ$ 是一个建立了全序关系的集合，也就是说， $Σ$ 中的任意两个不同的元素 $α$ 和 $β$ 都可以比较大小，要么 $α<β$ ，要么 $β<α$ （也就是 $α>β$ ）。字符集 $Σ$ 中的元素称为字符。
 
 ### 字符串
 
-一个**字符串** $S$ 是将 $n$ 个字符顺次排列形成的序列，$n$ 称为 $S$ 的长度，表示为 $|S|$。$S$ 的第 $i$ 个字符表示为 $S[i]$。（在有的地方，也会用 $S[i-1]$ 表示第 $i$ 个字符。）
+一个 **字符串**  $S$ 是将 $n$ 个字符顺次排列形成的序列， $n$ 称为 $S$ 的长度，表示为 $|S|$ 。 $S$ 的第 $i$ 个字符表示为 $S[i]$ 。（在有的地方，也会用 $S[i-1]$ 表示第 $i$ 个字符。）
 
 ### 子串
 
-字符串 $S$ 的**子串** $S[i..j]，i≤j$，表示 $S$ 串中从 $i$ 到 $j$ 这一段，也就是顺次排列 $S[i],S[i+1],\ldots,S[j]$ 形成的字符串。
+字符串 $S$ 的 **子串**  $S[i..j]，i≤j$ ，表示 $S$ 串中从 $i$ 到 $j$ 这一段，也就是顺次排列 $S[i],S[i+1],\ldots,S[j]$ 形成的字符串。
 
-有时也会用 $S[i..j]$, $i>j$ 来表示空串。
+有时也会用 $S[i..j]$ , $i>j$ 来表示空串。
 
 ### 子序列
 
-字符串 $S$ 的**子序列**是从 $S$ 中将若干元素提取出来并不改变相对位置形成的序列，即 $S[p_1],S[p_2],\ldots,S[p_k]$，$1\le p_1<p_2<\cdots<p_k\le|S|$。
+字符串 $S$ 的 **子序列** 是从 $S$ 中将若干元素提取出来并不改变相对位置形成的序列，即 $S[p_1],S[p_2],\ldots,S[p_k]$ ， $1\le p_1<p_2<\cdots<p_k\le|S|$ 。
 
 ### 后缀
 
-**后缀**是指从某个位置 $i$ 开始到整个串末尾结束的一个特殊子串。字符串 $S$ 的从 $i$ 开头的后缀表示为 $Suffix(S,i)$，也就是 $Suffix(S,i)=S[i..|S|]$。
+ **后缀** 是指从某个位置 $i$ 开始到整个串末尾结束的一个特殊子串。字符串 $S$ 的从 $i$ 开头的后缀表示为 $Suffix(S,i)$ ，也就是 $Suffix(S,i)=S[i..|S|]$ 。
 
-**真后缀** 指除了 $S$ 本身的 $S$ 的后缀。
+ **真后缀** 指除了 $S$ 本身的 $S$ 的后缀。
 
 ### 字典序
 
-以第 $i$ 个字符作为第 $i$ 关键字进行大小比较，空字符小于字符集内任何字符（即：$a<aa$）。
+以第 $i$ 个字符作为第 $i$ 关键字进行大小比较，空字符小于字符集内任何字符（即： $a<aa$ ）。
 
 ### 回文串
 
-**回文串** 是正着写和倒着写相同的字符串，即满足 $\forall 1\le i\le|s|, s[i]=s[|s|+1-i]$ 的 $s$。
+ **回文串** 是正着写和倒着写相同的字符串，即满足 $\forall 1\le i\le|s|, s[i]=s[|s|+1-i]$ 的 $s$ 。
 
 ## 字符串的存储
 
-1. 使用 `char` 数组存储，用空字符 `\0` 表示字符串的结尾。（C 风格字符串）
-2. 使用 C++ 标准库提供的 [`string` 类](../lang/csl/string.md)。
-3. 字符串常量可以用字符串字面值（用双引号括起来的字符串）表示。
+1.  使用 `char` 数组存储，用空字符 `\0` 表示字符串的结尾。（C 风格字符串）
+2.  使用 C++ 标准库提供的 [ `string` 类](../lang/csl/string.md) 。
+3.  字符串常量可以用字符串字面值（用双引号括起来的字符串）表示。
 
 ## 参考资料
 
-[后缀数组 by.徐智磊](https://wenku.baidu.com/view/0dc03d2b1611cc7931b765ce0508763230127479.html)
\ No newline at end of file
+ [后缀数组 by. 徐智磊](https://wenku.baidu.com/view/0dc03d2b1611cc7931b765ce0508763230127479.html) 
diff --git a/docs/string/match.md b/docs/string/match.md
index 289c3343..64b5a727 100644
--- a/docs/string/match.md
+++ b/docs/string/match.md
@@ -24,14 +24,14 @@
 
 ```cpp
 std::vector<int> match(char *a, char *b, int n, int m) {
-	std::vector<int> ans;
-	for (i = 0; i < n - m + 1; i++) {
-		for (j = 0; j < m; j++) {
-			if (a[i + j] != b[j]) break;
-		}
-		if (j == m) ans.push_back(i);
-	}
-	return ans;
+  std::vector<int> ans;
+  for (i = 0; i < n - m + 1; i++) {
+    for (j = 0; j < m; j++) {
+      if (a[i + j] != b[j]) break;
+    }
+    if (j == m) ans.push_back(i);
+  }
+  return ans;
 }
 ```
 
-- 
2.11.0