字符串

哈希

KMP

• 前缀数组

  def get_prefix(t):
      m = len(t)
      prefix = [0] * m
      prefix[0] = -1
  
      j = 0
      k = -1
      while j < m - 1:
          if k < 0 or t[j] == t[k]:
              j += 1
              k += 1
  
              if t[j] != t[k]:
                  prefix[j] = k
              else:
                  prefix[j] = prefix[k]
          else:
              k = prefix[k]
      return prefix

• KMP

  def KMP(s, t):
      n = len(s)
      m = len(t)
      prefix = get_prefix(t)
  
      i = 0
      j = 0
      while i < n and j < m:
          if j < 0 or s[i] == t[j]:
              i += 1
              j += 1
          else:
              j = prefix[j]
  
      if j >= m:
          return i - m
      else:
          return -1

manacher

• 问题
  给定一个长度为n的字符串s，找出所有的回文子串。

• 定义

  • d1：以位置i为中心的长度为奇数的回文串个数。
  • d2：以位置i为中心（右侧）的长度为偶数的回文串个数。

• 朴素算法

  d1 = [0] * n
  d2 = [0] * n
  for i in range(0, n):
      k = 1
      while 0 <= i - k and i + k < n and s[i - k] == s[i + k]:
          k += 1
      d1[i] = k
  
      k = 0
      while 0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k]:
          k += 1
      d2[i] = k

• manacher算法

  d1 = [0] * n
  l, r = 0, -1
  for i in range(0, n):
      k = 1 if i > r else min(d1[l + r - i], r - i + 1)
      while 0 <= i - k and i + k < n and s[i - k] == s[i + k]:
          k += 1
      d1[i] = k
      k -= 1
      if i + k > r:
          l = i - k
          r = i + k

  d2 = [0] * n
  l, r = 0, -1
  for i in range(0, n):
      k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
      while 0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k]:
          k += 1
      d2[i] = k
      k -= 1
      if i + k > r:
          l = i - k - 1
          r = i + k

AC自动机

拓展

• 后缀数组
• 后缀自动机
• 回文自动机