Skip to content

Commit 631870e

Browse files
committed
feat: update 005
1 parent 58ee959 commit 631870e

File tree

1 file changed

+4
-4
lines changed

1 file changed

+4
-4
lines changed

note/005/README.md

+4-4
Original file line numberDiff line numberDiff line change
@@ -115,7 +115,7 @@ class Solution {
115115

116116
以上问题的传统思路大概是遍历每一个字符,以该字符为中心向两边查找,其时间复杂度为 `O(n2)`,效率很差。
117117

118-
1975年,一个叫 Manacher 的人发明了一个算法,Manacher 算法(中文名:马拉车算法),该算法可以把时间复杂度提升到 `O(n)`下面按我理解的思路来讲解其原理
118+
1975年,一个叫 Manacher 的人发明了 Manacher 算法(中文名:马拉车算法),该算法可以把时间复杂度提升到 `O(n)`下面我以我理解的思路来讲解其原理
119119

120120
由于回文串的奇偶行不确定,比如 `lol` 是奇回文,而 `lool` 是偶回文,马拉车算法的第一步就是对其进行预处理,做法就是在每个字符两侧都加上一个特殊字符,一般就是不会出现在原串中的即可,我们可以选取 `#`,那么
121121

@@ -134,13 +134,13 @@ lool -> #l#o#o#l#
134134

135135
| str | # | l | # | o | # | l | # | l | # | o | # | o | # | l | # |
136136
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
137-
| len | 1 | 2 | 1 | 4 | l | 2 | 3 | 2 | 1 | 2 | 5 | 2 | 1 | 2 | 1 |
137+
| len | 1 | 2 | 1 | 4 | l | 2 | 5 | 2 | 1 | 2 | 5 | 2 | 1 | 2 | 1 |
138138

139139
可以发现 `len[i] - 1` 就等于该回文串在原串中的长度。
140140

141-
证明:在转换后的字符串 `str` 中,那么对于以 `str[i]` 为中心的最长回文串的长度为 `2 * len[i] - 1`,其中又有 `len[i]` 个分隔符,所以在原字符串中的长度就是 `len[i] - 1`
141+
证明:在转换后的字符串 `str` 中,那么对于以 `str[i]` 为中心的最长回文串的长度为 `2 * len[i] - 1`其中又有 `len[i]` 个分隔符,所以在原字符串中的回文串长度就是 `len[i] - 1`
142142

143-
那么我们剩下的工作就是求 `len` 数组
143+
那么我们剩下的工作就是求 `len` 数组
144144

145145

146146

0 commit comments

Comments
 (0)