一、概念
字符串分为主串、模式串。
在字符串T中查找字符串 P，T 就是主串，P 就是模式串，设 T 的长度为n，P 的长度为m。
二、单模式串算法
单模式串算法，即一个串跟一个串匹配。包括：BF算法， RK算法， BM算法，KMP算法。
2.1、BF算法
2.1.1、概念：
在BF中，每次在比较模式串和主串子串匹配的时候，都需要一次比较，RK则使用哈希算法对上述过程优化。
2.2.2、基本实现和特性：
通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小，如果某个子串的哈希值与模式串相等，就说明子串和模式串匹配。
具体步骤如下：
1、计算子串的哈希值；
2、模式串哈希值和子串哈希值的比较。
重点：
1、设计哈希算法，扫描一遍计算 n-m+1 子串的哈希值；
2、设计的哈希算法健壮性比较强，可以解决模式串比较长，哈希值很大的情况；
3、哈希冲突。
最好时间复杂度为O（n）， 最坏的时间复杂度O（n*m）
2.2、BM算法
2.2.1、概念：
把主串和模式串的匹配过程看出模式串不停往右滑动，当遇到不匹配的字符时，模式串往后滑动一位，然后从模式串的第一位开始匹配，BM算法借助一些规律将模式串向右多滑动几位。
2.2.2、基本实现和特性：
算法步骤：
1、模式字符串的匹配顺序是从右向左：
（1）首先将P和T对齐，即p[0] 和 t[0] 对齐
（2）然后匹配从模式字符串P的的最右端字符开始，即判断p[m] 和 t[m] 是否匹配；如果匹配成功，则向左移动判断 p[m-1] 和 t[m-1] 是否匹配，如此循环下去；如果匹配不成功，则进行字符串滑移。
2、字符串滑移启发式策略：
（1）坏字符移动启发式策略
（2）好后缀移动启发式策略
两种策略的使用：如果同时满足两种策略使用条件时，选两者中较大的作为模式串向右滑移的距离。
最坏情况下时间复杂度O（n*m），最好情况下 O（n/m）
2.3、KMP算法
2.3.1、概念：
跟BM算法非常近似，在模式串和主串匹配的过程中，当遇到那些不可匹配的字符时，希望有某些规律模式串往右多滑动几位，跳过那些肯定不会匹配的情况。
2.3.2、基本实现和特性：
构建模式串 next 数组，用来存储模式串中的每个前缀的最长匹配子串的结尾字符下标。时间复杂度 O(m+n)。
三、多模式串算法
多模式串算法包括Trie树，AC自动机。
3.1、Trie树
3.1.1、概念：
Trie树也称为字典树，是一个树形结构，专门用于处理字符串匹配的数据结构，用来解决在一组字符集合中快速查找某个字符串的问题。本质是利用字符串之间的公共前缀，将重复的前缀合并在一起。
典型应用：被搜索引擎系统用于文本词频统计。
3.1.2、基本实现和特性：
搜索Trie树的方法为：
1、从根结点开始一次搜索；
2、取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
3、在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索；
4、迭代过程......
5、在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
基本性质：
1、根节点不包括字符，除根结点之外每一个结点都只包含一个字符；
2、从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串；
3、每个结点的所有子结点包含的字符都不相同；
4、Trie树是一个多叉树；
5、Trie树是多主串匹配算法；
关键操作：
1、将字符集构建Trie树，时间复杂度O（n）
2、在Trie树中查询一个字符串，时间复杂度O（k），k是要查找字符的长度
缺点：Trie树比较消耗内存，典型的空间换时间思想。
3.2、AC自动机
3.2.1、概念：
AC自动机就是在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上。
3.2.2、基本实现和特性：
1、AC自动机的构建：
（1）将多个模式串建成Trie树
（2）在Trie树上构建失败指针（类似KMP的next指针）
2、在AC自动机上匹配主串。
四、常见面试题
例题1：
151. 翻转字符串里的单词 https://leetcode-cn.com/problems/reverse-words-in-a-string/
给定一个字符串，逐个翻转字符串中的每个单词。
说明：
无空格字符构成一个 单词 。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
示例 1：
输入："the sky is blue"
输出："blue is sky the"
示例 2：
输入：" hello world! "
输出："world! hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入："a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
示例 4：
输入：s = " Bob Loves Alice "
输出："Alice Loves Bob"
示例 5：
输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"
思路：
split + reverse + join
时间复杂度： O（n）
空间复杂度： O（1）
代码实现：
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(s.split()[::-1])
例题2：
557. 反转字符串中的单词 III https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
思路：
思路： split + reverse + join + reverse
时间复杂度： O（n）
空间复杂度： O（1）
代码实现：
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(s.split()[::-1])[::-1]
例题3：541. 反转字符串 II https://leetcode-cn.com/problems/reverse-string-ii/
给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
思路：
双指针法。先将字符串转换成数组，依次循环数组，左指针指向当前元素，右指针指向第k-1个元素，对左右指针内的元素依次进行交换，左右指针分别+1， -1，直到左指针大于等于右指针。最后字符串拼接数组，返回字符串对象。
T：O（logn）
S：O（1）
时间复杂度： O（logn）
空间复杂度： O（1）
代码实现：
class Solution:
def reverseStr(self, s: str, k: int) -> str:
s = list(s)
for i in range(0, len(s), 2 * k):
left = i
right = i + k - 1 if i + k - 1 < len(s) else len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ''.join(s)
例题4：1021. 删除最外层的括号 https://leetcode-cn.com/problems/remove-outermost-parentheses/
有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。
如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。
示例 1：
输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
示例 2：
输入："(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
示例 3：
输入："()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。
思路：
思路：借助辅助栈，如果辅助栈里有元素，就说明当前遍历的括号不是最外层的括号，可以加入到返回的结果集中。具体的处理为：遇到左括号，先判断栈，有则加入到返回结果集中，然后加入栈中。遇到右括号，则先弹出栈，然后判断栈中是否有元素，有则加入到返回的结果集中。
时间复杂度： O（n）n为字符串的长度
空间复杂度： O（n）
代码实现：
class Solution:
def removeOuterParentheses(self, S: str) -> str:
re, stack = '', []
for s in S:
if s == '(':
if stack:
re += s
stack.append(s)
if s == ')':
stack.pop()
if stack:
re += s
return re
例题5：389. 找不同 https://leetcode-cn.com/problems/find-the-difference/
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例 1：
输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。
示例 2：
输入：s = "", t = "y"
输出："y"
示例 3：
输入：s = "a", t = "aa"
输出："a"
示例 4：
输入：s = "ae", t = "aea"
输出："a"
思路：
方式一：用Counter字典做差
方式二：位运算，^
方式三：求和， ord求得acii码求和，然后chr转码
方式四：工具类， （xor异或，reduce累积求和，map函数映射）
时间复杂度： O（n）n为字符串的长度
空间复杂度： O（1）
代码实现：
# 方式一：counter做差
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
return list(collections.Counter(t) - collections.Counter(s))[0]
# 方式二：位运算
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
res = 0
for i in s:
res ^= ord(i)
for i in t:
res ^= ord(i)
return chr(res)
# 方式三：求和：
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
# 求和
res_s, res_t = 0, 0
for i in s:
res_s += ord(i)
for i in t:
res_t += ord(i)
return chr(res_t - res_s)
# 方式四：根据工具类， xor异或，reduce累积求和， map函数映射
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
return chr(reduce(xor, map(ord, s+t)))
撰写记录
2020.12.30-06:46:00-第一次撰写
2021.01.03-07:38:00-第二次撰写
2021.01.10-10:44:00-第三次撰写
2021.02.15-15:32:00-第四次撰写
