2021-11-25：给定两个字符串 s1 和 s2，返回在 s1 中有多少个子串等于 s2。来自美团。？

2021-11-25：给定两个字符串 s1 和 s2，返回在 s1 中有多少个子串等于 s2。来自美团。

Golang 答疑
回答·4
最热
最新
  • kmp 单模匹配算法 时间复杂度 O（n）
  • 循环 s1 长度，取出 s2 首个字符和 s2 长度，匹配到首个字符一样，进行累计 s1 长度取值，有多个字符和 s2 首字符一致，则多次累计，总循环次数为 s1 长度数量。
  • 类似滑动窗口算法，不难。
  • 使用 Rabin Karp 算法，用两套进制和模数可以避免 hash 冲突，时间 o(n)，空间 1