https://leetcode.com/problems/implement-strstr/
还是有必要掌握的一个算法。
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
https://brickmaker.github.io/2018/08/19/kmp/
https://oi-wiki.org/string/kmp/#knuth-morris-pratt

个人解答

  1. class Solution:
  2.     def strStr(self, s: str, p: str) -> int:
  3.         def genLPS(s):
  4.             lps = [0] * len(s)
  5.             i = 1
  6.             l = 0
  7.             while i < len(s):
  8.                 if s[i] == s[l]:
  9.                     l += 1
  10.                     lps[i] = l
  11.                     i += 1
  12.                 elif l > 0:
  13.                     l = lps[l - 1]
  14.                 else:
  15.                     lps[i] = 0
  16.                     i += 1
  17.             return lps
  19.         lps = genLPS(p)
  20.         # print(lps)
  22.         if not p:
  23.             return 0
  25.         i, j = 0, 0
  27.         while i < len(s):
  28.             if s[i] == p[j]:
  29.                 i += 1
  30.                 j += 1
  31.                 if j == len(p):
  32.                     return i - j
  33.             elif j > 0:
  34.                 j = lps[j - 1]
  35.             else:
  36.                 i += 1
  38.         return -1

题目分析

其实就是KMP算法的典型应用。
关于这个最长相同前缀后缀数组（LPS）的生成，可以考虑 lps[i] 表示 [0, i] 区间的，也可以表示 [0, i - 1] 区间的，就实现来说，前者更符合直觉，但是后者写起来可能更加简洁，更trick。

至于子字符串的问题，其实就是求s + ‘#’ + p这个字符串的LPS，因为求LPS的过程是个在线过程，所以，上述代码的 genLPS 函数和外部的代码高度相似（除了没有存lps数组）。

整个代码需要考虑好多关注点，尤其是，在之前判断or在之后判断？何时终止？都是需要想明白的。