text: # AUTOGENERATED! DO NOT EDIT! File to edit: nbs/00_algos.ipynb (unless otherwise specified).
  
  __all__ = ['levenshtein_distance', 'n_gram_overlap', 'longest_common_substring']
  
  # Cell
  
  # This code was taken from https://gist.github.com/kylebgorman/1081951/bce3de986e4b05fc0b63d4d9e0cfa4bde6664365
  def _dist(A, B, insertion, deletion, substitution):
      D = np.zeros((len(A) + 1, len(B) + 1))
      for i in range(len(A)):
          D[i + 1][0] = D[i][0] + deletion
      for j in range(len(B)):
          D[0][j + 1] = D[0][j] + insertion
      for i in range(len(A)): # fill out middle of matrix
          for j in range(len(B)):
              if A[i] == B[j]:
                  D[i + 1][j + 1] = D[i][j] # aka, it's free.
              else:
                  D[i + 1][j + 1] = min(D[i + 1][j] + insertion,
                                        D[i][j + 1] + deletion,
                                        D[i][j]     + substitution)
      return D
  
  def levenshtein_distance(l1, l2, normalize=False):
      dist = _dist(l1, l2, 1, 1, 1)[-1][-1]
      if normalize:
          return 1. - dist / max(len(l1), len(l2))
      else:
          return dist
  
  # Cell
  # implementation inspired from https://yunjinhan.github.io/2017/04/n-gram-overlap
  
  def _n_grams(l, n):
      grams = []
      for i in range(0, len(l) + 1 - n):
          grams.append(l[i:i + n])
  
      return grams
  
  def n_gram_overlap(l1, l2, n, normalize=False):
      l1_grams = _n_grams(l1, n)
      l2_grams = _n_grams(l2, n)
  
      overlap = len(set(l1_grams) & set(l2_grams))
      if normalize:
          return overlap / max(len(l1_grams), len(l2_grams))
      else:
          return overlap
  
  # Cell
  
  # from geeksforgeeks: https://www.geeksforgeeks.org/longest-common-substring-dp-29/
  def _longest_common_substring(X, Y, m, n):
      LCSuff = [[0 for k in range(n+1)] for l in range(m+1)]
  
      # To store the length of
      # longest common substring
      result = 0
  
      # Following steps to build
      # LCSuff[m+1][n+1] in bottom up fashion
      for i in range(m + 1):
          for j in range(n + 1):
              if (i == 0 or j == 0):
                  LCSuff[i][j] = 0
              elif (X[i-1] == Y[j-1]):
                  LCSuff[i][j] = LCSuff[i-1][j-1] + 1
                  result = max(result, LCSuff[i][j])
              else:
                  LCSuff[i][j] = 0
      return result
  
  def longest_common_substring(l1, l2, normalize=False):
      lcs = _longest_common_substring(l1, l2, len(l1), len(l2))
      if normalize:
          return lcs / max(len(l1), len(l2))
      else:
          return lcs