正则表达式

---

• 1.字符串s是否可以匹配字符串p
• 2.字符串s匹配到的字符串p的子字符串信息

---

模式匹配

---

字符串s是否可以匹配字符串p
isMatch(s,p)

---

动态规划

---

dp[i][j] 代表 s[0:i-1] 是否 和 p[0:j-1] 匹配
情况:

• 1.s[i] == p[j]
• 2.p[j] == ‘*’
• 3.p[j] == ‘?’

转移方程:

• 1.dp[i][j] = dp[i-1][j-1]
• 2.dp[i][j] = dp[i-1][j] || dp[i][j-1]
• 3.dp[i][j] = dp[i-1][j-1]

---

KMP算法

---

next函数

---

BM算法

---

• 1.坏字符规则

  • 1.坏字符在模式串中没有出现，则直接移动到坏字符后
  • 2.坏字符在模式串中出现，则两者对齐

  坏字符规则公式:后移位数 = 坏字符的位置 - 模式串中坏字符的上一次出现位置

• 2.好后缀规则

  • 1.好后缀在模式串中出现，则将两者对齐，出现多次，与最右侧的对齐
  • 2.好后缀只在模式串中出现一次，则寻找其最大字串作为后缀

  好后缀规则公式:后移位数 = 好后缀的位置 - 模式串中上一次出现的位置

---