greppy

#!/usr/bin/env python3
from sys import stdin
from sys import argv
from collections import defaultdict

# Adapted from Intro to Algorithms by CLRS.
# A string matching automata similar to grep.

def computeTransitionFunction(pattern):
  m = len(pattern)
  alphabet = set(pattern)
  transitions = defaultdict(lambda: 0) # if the letter is not in the pattern go back to state 0
  for q in range(m):
    for a in alphabet:
      k = min(m , q + 1)
      while not (pattern[:q] + a).endswith(pattern[:k]):
        k -= 1
      transitions[q, a] = k
  return transitions

if len(argv) != 2:
  print('usage: ' + argv[0] + ' <pattern>')
else:
  pattern = argv[1]
  t = computeTransitionFunction(pattern)
  for line in stdin:
    q = 0
    for a in line:
      q = t[q, a]
      if q == len(pattern):
        print(line[:-1])
        break