#!/usr/bin/env python
# -*- encoding: japanese.euc_jp -*-

# pgrep.py - parallel grep for thousand of constant patterns
#
# usage: $ ./pgrep.py words [file1 file2 ...]
#        (words file contains a word per line)


##  Letter
##
class Letter:
  
  def __init__(self):
    self.newthread = []
    self.threads = {}
    return
  
  def __repr__(self):
    return '<Letter: new=%s, threads=%s>' % (self.newthread, self.threads)
  
  def addnew(self, t):
    self.newthread.append(t)
    return
  
  def addnext(self, t, next):
    self.threads[t] = next
    return
  
  def proceed(self, t):
    return self.threads.get(t)


##  ParallelDict
##
class ParallelDict:

  # proc: a callback function which takes one value.
  def __init__(self):
    self.dic = {}
    self.tid = 0
    return
  
  def debug(self):
    for (c,letter) in self.dic.iteritems():
      print c, letter
    return
  
  def getid(self):
    self.tid += 1
    return self.tid

  # s: pattern (string)
  # prop: a value which is passed to the callback when the pattern is found.
  def add(self, s):
    t = 0
    for (i,c) in enumerate(s):
      letter = self.dic.get(c, Letter())
      if t == 0:
        t = self.getid()
        letter.addnew(t)
      else:
        if i == len(s)-1:
          letter.addnext(t, s)
        else:
          nt = self.getid()
          letter.addnext(t, nt)
          t = nt
      self.dic[c] = letter
    return

  def search(self, s):
    threads = []
    for (i,c) in enumerate(s):
      #print "find:", c, threads
      try:
        letter = self.dic[c]
      except KeyError:
        threads = []
        continue
      threads1 = letter.newthread[:]
      for t in threads:
        x = letter.proceed(t)
        if x:
          if isinstance(x, int):
            threads1.append(x)
          else:
            yield (i-len(x)+1, x)
      threads = threads1
    return


# main
if __name__=="__main__":
  import sys, fileinput
  # read words file
  D = ParallelDict()
  f = file(sys.argv[1])
  for line in f.xreadlines():
    D.add(unicode(line.strip()))
  f.close()
  #D.debug()
  del sys.argv[1]
  for line in fileinput.input():
    line = unicode(line.strip())
    for (i,t) in D.search(line):
      print line, i, t