Quick and dirty trie

trie

class node:
  def __init__(self):
    self.is_end = False
    self.table = {}

  def add(self, c):
    if c not in self.table:
      self.table[c] = node()
    return self.table[c]

  def next(self, c):
    return self.table.get(c)

class trie:
  def __init__(self):
    self.root = node()

  def add(self, s):
    current = self.root
    for c in s:
      current = current.add(c)
    current.is_end = True

  def match(self, s, i):
    current = self.root
    for j in range(i, len(s)):
      current = current.next(s[j])
      if current == None:
        return
      elif current.is_end:
        yield (i,j)