或者是：

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:s = ""for i in zip(*strs): # 直接取出所有字符串的第i列if len(set(i)) == 1:s += i[0]else:break           return s

二、单模式串匹配算法

参考《算法通关手册》单模式串匹配篇

2.1 Brute Force 算法（暴力匹配）

2.1.1 算法介绍

• Brute Force 算法：简称为 BF 算法。中文意思是暴力匹配算法，也可以叫做朴素匹配算法。

• BF 算法思想：对于给定文本串 T 与模式串 p，从文本串的第一个字符开始与模式串 p 的第一个字符进行比较，如果相等，则继续逐个比较后续字符，否则从文本串 T 的第二个字符起重新和模式串 p 进行比较。依次类推，直到模式串 p 中每个字符依次与文本串 T 的一个连续子串相等，则模式匹配成功。否则模式匹配失败。

• Brute Force 算法步骤

  1. 对于给定的文本串 T 与模式串 p，求出文本串 T 的长度为 n，模式串 p 的长度为 m。
  2. 同时遍历文本串 T 和模式串 p，先将 T[0] 与 p[0] 进行比较。
     1. 如果相等，则继续比较 T[1] 和 p[1]。以此类推，一直到模式串 p 的末尾 p[m - 1] 为止。
     2. 如果不相等，则将文本串 T 移动到上次匹配开始位置的下一个字符位置，模式串 p 则回退到开始位置，再依次进行比较。
  3. 当遍历完文本串 T 或者模式串 p 的时候停止搜索。

2.1.2 代码实现

def bruteForce(T: str, p: str) -> int:n, m = len(T), len(p)i, j = 0, 0                     # i 表示文本串 T 的当前位置，j 表示模式串 p 的当前位置while i < n and j < m:          # i 或 j 其中一个到达尾部时停止搜索if T[i] == p[j]:            # 如果相等，则继续进行下一个字符匹配i += 1					# i和j同步右移j += 1else:i = i - (j - 1)         # 如果匹配失败则将 i 移动到上次匹配开始位置的下一个位置，j = 0                   # 匹配失败 j 回退到模式串开始位置if j == m:return i - j                # 匹配成功，返回匹配的开始位置else:return -1                   # 匹配失败，返回 -1

2.2.3 算法分析

  BF 算法非常简单，容易理解，但其效率很低。主要是因为在匹配过程中可能会出现回溯：当遇到一对字符不同时，模式串 p 直接回到开始位置，文本串也回到匹配开始位置的下一个位置，再重新开始比较。

• 最坏时间复杂度为 O(m×n)O(m \times n)O(m×n)。在回溯之后，文本串和模式串中一些部分的比较是没有必要的。由于这种操作策略，导致 BF 算法的效率很低。最坏情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况，每轮比较需要进行 m 次字符对比，总共需要进行 n - m + 1 轮比较，总的比较次数为 m * (n - m + 1) 。

• 最佳时间复杂度是 O(m)O(m)O(m)。最理想的情况下（第一次匹配直接匹配成功）。

• 平均时间复杂度为 O(n+m)O(n + m)O(n+m)。在一般情况下，根据等概率原则，平均搜索次数为 (n+m)2\frac{(n + m)}{2}2(n+m)​。

2.2 KMP 算法介绍

参考：

• 《算法通关手册：KMP 算法》
• 《如何更好地理解和掌握 KMP 算法?》
• 《【宫水三叶】简单题学 KMP 算法》

  KMP 算法：全称叫做 「Knuth Morris Pratt 算法」，是由它的三位发明者 Donald Knuth、James H. Morris、 Vaughan Pratt 的名字来命名的。KMP 算法是他们三人在 1977 年联合发表的。

   KMP 算法思想：对于给定文本串 T 与模式串 p，当发现文本串 T 的某个字符与模式串 p 不匹配的时候，可以利用匹配失败后的信息，尽量减少模式串与文本串的匹配次数，避免文本串位置的回退，以达到快速匹配的目的。

2.2.1 朴素匹配算法的缺陷

  在朴素匹配算法的匹配过程中，我们分别用指针 i 和指针 j 指示文本串 T 和模式串 p 中当前正在对比的字符。当发现文本串 T 的某个字符与模式串 p 不匹配的时候，j 回退到开始位置，i 回退到之前匹配开始位置的下一个位置上（下图的B），继续匹配，直到能够与匹配串对上位置（下图第二个A），如下图所示。

  那么有没有哪种算法，可以让 i 不发生回退，一直向右移动呢？

2.2.1 改进算法：KMP

  如果我们可以通过每一次的失配而得到一些「信息」，并且这些「信息」可以帮助我们跳过那些不可能匹配成功的位置，那么我们就能大大减少模式串与文本串的匹配次数，从而达到快速匹配的目的。

1. 每一次失配所告诉我们的信息是：主串的某一个子串等于模式串的某一个前缀。

• 比如文本串 T[i: i + m] 与模式串 p 的失配是下标位置 j 上发生的，那么文本串 T 从下标位置 i 开始连续的 j - 1 个字符，一定与模式串 p 的前 j - 1 个字符一模一样，即：T[i: i + j] == p[0: j]。

• 例如上图中，失配是在下标i+5这个位置发生的，那么失配位置的前5个字符，一定与模式串 p 的前 5 个字符一模一样，即："ABCAB" == "ABCAB"。

2. 模式串的前 5 个字符中，前 2 位前缀和后 2 位后缀又是相同的，即 "AB" == "AB"。

  所以根据上面的信息，我们可以推出：文本串子串的后 2 位后缀和模式串子串的前 2 位是相同的，即 T[i + 3: i + 5] == p[0: 2]，而这部分（即下图中的蓝色部分）是之前已经比较过的，不需要再比较了，可以直接跳过。

  那么我们就可以将文本串中的 T[i + 5] 对准模式串中的 p[2]，继续进行对比。这样 i 就不再需要回退了，可以一直向右移动匹配下去。在这个过程中，我们只需要将模式串 j 进行回退操作即可。

  实际上，我们会创建一个next数组作为「部分匹配表」，next[j] 表示的含义是：**记录下标 j 之前（包括 j）的模式串 p 中，最长相等前后缀的长度。**下一节会详细说明。
   由于模式串数组中，next[4] == 2，所以不用回退 i，而是将 j 移动到下标为 2 的位置，让 T[i + 5] 直接对准 p[2]，然后继续进行比对。

下图参考《【宫水三叶】简单题学 KMP 算法》

  也就是说，匹配失败时，匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在，则跳转到「前缀」的下一个位置继续往下匹配：

  跳转到下一匹配位置后，尝试匹配，发现两个指针的字符对不上，并且此时匹配串指针前面不存在相同的「前缀」和「后缀」，这时候只能回到匹配串的起始位置重新开始：

  KMP 算法就是使用了这样的思路，对模式串 p 进行了预处理，计算出一个 「部分匹配表」(也叫PMT:Partial Match Table)**，用一个数组 next 来记录。然后在每次失配发生时，不回退文本串的指针 i，而是根据「部分匹配表」中模式串失配位置 j 的前一个位置的值，即 next[j - 1] 的值来决定模式串可以向右移动的位数。

• KMP 利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配
• KMP 的原串指针不会进行回溯（没有朴素匹配中回到下一个「发起点」的过程）

2.2.3 next 数组

  上文提到的「部分匹配表PMT」，也叫做「前缀表」，在 KMP 算法中使用 next 数组存储。next[j] 表示的含义是：记录下标 j 之前（包括 j）的模式串 p 中，最长相等前后缀的长度。 也可以理解为，PMT中的值是 字符串的前缀集合与后缀集合的交集中最长元素的长度。

• 前缀：
  • 如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。
  • 例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。
• 后缀：
  • 若有A=SB， 其中S是任意的非空字符串，那就称B为A的后缀
  • 例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。
• 对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}， 两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。
• 要注意的是，字符串本身并不是自己的前缀或者后缀。
  

举个例子来说明一下，以 p = "ABCABCD" 为例。

• next[0] = 0，因为 "A" 中无有相同前缀后缀，最大长度为 0。
• next[1] = 0，因为 "AB" 中无相同前缀后缀，最大长度为 0。
• next[2] = 0，因为 "ABC" 中无相同前缀后缀，最大长度为 0。
• next[3] = 1，因为 "ABCA" 中有相同的前缀后缀 "a"，最大长度为 1。
• next[4] = 2，因为 "ABCAB" 中有相同的前缀后缀 "AB"，最大长度为 2。
• next[5] = 3，因为 "ABCABC" 中有相同的前缀后缀 "ABC"，最大长度为 3。
• next[6] = 0，因为 "ABCABCD" 中无相同前缀后缀，最大长度为 0。

  同理也可以计算出 "ABCABDEF" 的前缀表为 [0, 0, 0, 1, 2, 0, 0, 0]。"AABAAAB" 的前缀表为 [0, 1, 0, 1, 2, 2, 3]。"ABCDABD" 的前缀表为 [0, 0, 0, 0, 1, 2, 0]。

  在之前的例子中，当 p[5] 和 T[i + 5] 匹配失败后，根据模式串失配位置 j 的前一个位置的值，即 next[4] = 2，我们直接让 T[i + 5] 直接对准了 p[2]，然后继续进行比对，如下图所示。

但是这样移动的原理是什么？

如果文本串 T[i: i + m] 与模式串 p 的失配是在第 j 个下标位置发生的，那么：

• 文本串 T 从下标位置 i 开始连续的 j 个字符，一定与模式串 p 的前 j 个字符一模一样，即：T[i: i + j] == p[0: j]（上图中的"ABCAB" == "ABCAB"）。

• 而如果模式串 p 的前 j 个字符中，前 k 位前缀和后 k 位后缀相同，（"ABCAB"中有相同的前后缀"AB"，即k=2）那么可以断言：文本串中i指针失配位置之前的 k 位（“AB”）一定与模式字符串的第0位至第 k位是相同的（“AB”），即长度为 k的后缀与前缀相同。

• 这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将j指针指向模式字符串的next[j −1]位即可（表示模式串中，前j-1个子符里，最长相同前后缀的长度k）。

其实相当于因为模式串存在相同的前后缀，所以失配后，模式串不用退回起始位置，退到相同前缀的下一位置就行。

2.2.4 next 数组的构造

  其实，求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为文本串串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。
  具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。 在任一位置，能匹配的最长长度就是当前位置的next值。如下图所示。

数组下标从0开始，所以图中应该是next[5]=4，以此类推。下图模式串有next=[0, 0, 1, 2, 3, 4, 0, 1]

这样我们就可以使用KMP本身的匹配原理来计算next数组。

• 我们将模式串p本身即作为文本串也作为模式串，同样用指针i和j来遍历。因为文本串第一个位置即使匹配上 ，也有next[0]=0，而不等于1，所以初始时令j = 0，i = 1。
• 遍历文本串和模式串：
  • 如果 p[i] != p[j]，说明文本串在此位置失配，同上面所讲， i 不动，模式串指针 j 不断回退到 next[j - 1] 位置。
    • 如果回退几次后，有 p[i] == p[j] ，说明匹配上了一个字符，令j右移，此时此时 j 既是前缀下一次进行比较的下标位置，又是当前最长前后缀的长度，所以next[i]=j。最后移动指针i遍历下一个位置；
    • 如果一直回退到j=0，表示文本串在i位置匹配不到任何一个字符，next[i]=0=j，i+=1；
  • 如果 p[i] == p[j]，同样先将 j += 1，next[i]=j，i+=1；

• 如果p[j]==p[i]，j先后移，next[i]=j，然后i后移；
• 如果不匹配，前缀指针回退，退到前一位置的next值，即j=next[j-1]，不停回退，直到p[j]==p[i]，或者j=0表示退到模式串开头位置，此时next[i]=0（因为j=0，所以依旧有next[i]=j），表示没有匹配的共同前后缀。
  
  
  
  

2.2.5 KMP 算法整体步骤和代码实现

1. 根据 next 数组的构造步骤生成「前缀表」next。
2. 使用两个指针 i、j，其中 i 指向文本串中当前匹配的位置，j 指向模式串中当前匹配的位置。初始时，i = 0，j = 0。
3. 循环判断模式串前缀是否匹配成功，如果模式串前缀匹配不成功，将模式串进行回退，即 j = next[j - 1]，直到 j == 0 时或前缀匹配成功时停止回退。
4. 如果当前模式串前缀匹配成功，则令模式串向右移动 1 位，即 j += 1。
5. 如果当前模式串 完全 匹配成功，则返回模式串 p 在文本串 T 中的开始位置，即 i - j + 1。
6. 如果还未完全匹配成功，则令文本串向右移动 1 位，即 i += 1，然后继续匹配。
7. 如果直到文本串遍历完也未完全匹配成功，则说明匹配失败，返回 -1。

# 生成 next 数组
# next[j] 表示下标 j 之前的模式串 p 中，最长相等前后缀的长度
def generateNext(p: str):m = len(p)next = [0 for _ in range(m)]                # 初始化数组元素全部为 0left = 0                                    # left 表示前缀串开始所在的下标位置for right in range(1, m):                   # right 表示后缀串开始所在的下标位置while left > 0 and p[left] != p[right]: # 匹配不成功, left 进行回退, left == 0 时停止回退left = next[left - 1]               # left 进行回退操作if p[left] == p[right]:                 # 匹配成功，找到相同的前后缀，先让 left += 1，此时 left 为前缀长度left += 1next[right] = left                      # 记录前缀长度，更新 next[right], 结束本次循环, right += 1return next# KMP 匹配算法，T 为文本串，p 为模式串
def kmp(T: str, p: str) -> int:n, m = len(T), len(p)next = generateNext(p)                      # 生成 next 数组j = 0                                       # j 为模式串中当前匹配的位置for i in range(n):                          # i 为文本串中当前匹配的位置while j > 0 and T[i] != p[j]:           # 如果模式串前缀匹配不成功, 将模式串进行回退, j == 0 时停止回退j = next[j - 1]if T[i] == p[j]:                        # 当前模式串前缀匹配成功，令 j += 1，继续匹配j += 1if j == m:                              # 当前模式串完全匹配成功，返回匹配开始位置return i - j + 1return -1                                   # 匹配失败，返回 -1            

2.2.5 KMP 算法分析

• KMP 算法在构造前缀表阶段的时间复杂度为 O(m)O(m)O(m)，其中 mmm 是模式串 p 的长度。
• KMP 算法在匹配阶段，是根据前缀表不断调整匹配的位置，文本串的下标 i 并没有进行回退，可以看出匹配阶段的时间复杂度是 O(n)O(n)O(n)，其中 nnn 是文本串 T 的长度。
• 所以 KMP 整个算法的时间复杂度是 O(n+m)O(n + m)O(n+m)，相对于朴素匹配算法的 O(n∗m)O(n * m)O(n∗m) 的时间复杂度，KMP 算法的效率有了很大的提升。

参考资料

• 【博文】从头到尾彻底理解 KMP - 结构之法 算法之道 - CSDN博客
• 【博文】字符串匹配的 KMP 算法 - 阮一峰的网络日志
• 【题解】多图预警👊🏻详解 KMP 算法 - 实现 strStr() - 力扣
• 【题解】「代码随想录」KMP算法详解 - 实现 strStr() - 力扣

三、单模式串匹配练习

3.1 单模式串匹配题目

3.2 找出字符串中第一个匹配项的下标

class Solution(object):def strStr(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""# KMP 匹配算法，haystack 为文本串，needle 为模式串m,n = len(haystack), len(needle)next = self.next(needle)  # 生成 next 数组j = 0                                             # j 为模式串中当前匹配的位置for i in range(m):                                # i 为文本串中当前匹配的位置while j > 0 and haystack[i] != needle[j]:     # 如果模式串前缀匹配不成功, 将模式串进行回退, j == 0 时停止回退j = next[j - 1]if haystack[i] == needle[j]:                  # 当前模式串前缀匹配成功，令 j += 1，继续匹配j += 1if j == n:                              	  # 当前模式串完全匹配成功，返回匹配开始位置return i - j + 1return -1def next(self,p):# 等同于模式串自己和自己匹配，只不过文本串从1开始（第一位匹配到结果也应该是0不是1），模式串从0开始next=[0 for _ in range(len(p))]j=0 # 模式串匹配起始位置，也是匹配到的长度for i in range(1,len(p)):#次序反过来，left右移，下一步判定就不对了#if p[left]==p[right]:#left+=1# 先判定不相等就回退，直到相等再右移模式串指针，进行下一步比较while j>0 and p[j]!=p[i]:j=next[j-1]if p[i]==p[j]:j+=1 			# 匹配上了，公共前后缀长度+1next[i]=jreturn next 

3.3 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

1. 思路一：官方题解
   

class Solution:def repeatedSubstringPattern(self, s: str) -> bool:return (s+s).find(s,1)!=len(s)

思路二：KMP（参考《算法通关手册》）
  我们知道 next[j] 表示的含义是：记录下标 j 之前（包括 j）的模式串 p 中，最长相等前后缀的长度。
  而如果整个模式串 p 的最长相等前后缀长度不为 0，即 next[len(p) - 1] != 0 ，则说明整个模式串 p 中有最长相同的前后缀。假设 next[len(p) - 1] == k，则说明 p[0: k] == p[m - k: m]。比如字符串 “abcabcabc”，最长相同前后缀为 “abcabc” = “abcabc”。

• 如果最长相等的前后缀是重叠的，比如之前的例子 “abcabcabc”。
  • 如果我们去除字符串中相同的前后缀的重叠部分，剩下两头前后缀部分（这两部分是相同的）。然后再去除剩余的后缀部分，只保留剩余的前缀部分。比如字符串 “abcabcabc” 去除重叠部分和剩余的后缀部分之后就是 “abc”。实际上这个部分就是字符串去除整个后缀部分的剩余部分。
  • 如果整个字符串可以通过子串重复构成的话，那么这部分就是最小周期的子串。
  • 我们只需要判断整个子串的长度是否是剩余部分长度的整数倍即可。也就是判断 len(p) % (len(p) - next[size - 1]) == 0 是否成立，如果成立，则字符串 s 可由 s[0: len(p) - next[size - 1]] 构成的子串重复构成，返回 True。否则返回 False。
• 如果最长相等的前后缀是不重叠的，那我们可将重叠部分视为长度为 0 的空串，则剩余的部分其实就是去除后缀部分的剩余部分，上述结论依旧成立。

class Solution:def repeatedSubstringPattern(self, s: str) -> bool:# 创建next数组le=len(s)if le==1:return Falsej=0next=[0 for _ in range(le)]for i in range(1,le):while j>0 and s[i]!=s[j]:j=next[j-1]if s[i]==s[j]:j+=1next[i]=j# next数组最后一位的值，表示模式串的最长相等前后缀长度。# 将其除去前后缀重叠部分和剩余的后缀部分，就是剩余前缀部分。# 这部分就是最小周期长度，可以被模式串长度整除if next[le-1]!=0 and le%(le-next[le-1])==0:return Truereturn False

3.4 重复叠加字符串匹配

  给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

输入：a = "abcd", b = "cdabcdab"
输出：3
解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。    

首先，可以分析复制次数的「下界」和「上界」为何值：

• 「下界」：至少将 a 复制长度大于等于 b 的长度，才有可能匹配
• 「上界」：由于主串是由 a 复制多次而来，并且是从主串中找到子串 b，因此可以明确子串的起始位置，不会超过 a 的长度。即长度越过 a 长度的起始匹配位置，必然在此前已经被匹配过了。由此，我们可知复制次数「上界」最多为「下界 + 1」
  

class Solution:def repeatedStringMatch(self, a: str, b: str) -> int:# 将b看做模式串，a最低重复次数是len([a]*count)=len(b)，即至少的是一样长# 最大重复次数是count+1。# 将a复制（n+1）次后匹配b，如果匹配下标超过n，则表示无法重复，否则返回countm,n=len(a),len(b)count=(n//m)+1 if n%m!=0 else n//ma=a*(count+1)idx=a.find(b)if idx ==-1:return -1else:idx=idx+n-1 # 匹配串的结束位置return count if idx

class Solution:def repeatedStringMatch(self, a: str, b: str) -> int:# 将b看做模式串，a最低重复次数是len([a]*count)=len(b)，即至少的是一样长# 最大重复次数是count+1。# 将a复制（n+1）次后匹配b，如果匹配下标超过n，则表示无法重复，否则返回countm,n=len(a),len(b)count=(n//m)+1 if n%m!=0 else n//ma=a*(count+1)idx=self.KMP(a,b)print(idx)if idx ==-1:return -1else:        return count if idx 0 and t[i] != p[j]:           # 如果模式串前缀匹配不成功, 将模式串进行回退, j == 0 时停止回退j = next[j - 1]if t[i] == p[j]:                        # 当前模式串前缀匹配成功，令 j += 1，继续匹配j += 1if j == n:                              # 当前模式串完全匹配成功，返回匹配结束位置return ireturn -1def next(self,p):# 等同于模式串自己和自己匹配看前缀，只不过文本串从1开始（第一位匹配到结果也应该是0不是1），模式串从0开始next=[0 for _ in range(len(p))]j=0 # 共同前缀下标for i in range(1,len(p)):#次序反过来，left右移，下一步判定就不对了#if p[left]==p[right]:#left+=1# 先判定不相等就回退，直到相等再右移模式串指针，进行下一步比较while j>0 and p[j]!=p[i]:j=next[j-1]if p[i]==p[j]:j+=1 # 匹配时，公共前后缀长度+1next[i]=j#print(next)return next

输入：sequence = "ababc", word = "ba"
输出：1
解释："ba" 是 "ababc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。

class Solution(object):def maxRepeating(self, sequence, word):""":type sequence: str:type word: str:rtype: int"""ans=0while (ans*word) in sequence:ans+=1return ans -1

class Solution(object):def maxRepeating(self, sequence, word):""":type sequence: str:type word: str:rtype: int"""m,n=len(sequence),len(word)max_count=m//nans,count=0,1while count<=max_count:temp=word*countif sequence.find(temp)!=-1:ans=max(ans,count)count+=1else:break            return ans

输入: s = "abcde", goal = "cdeab"
输出: true

class Solution(object):def rotateString(self, s, goal):""":type s: str:type goal: str:rtype: bool"""return goal in s+s if len(s)==len(goal) else False