#!/usr/bin/env python2.6

def buildCouples (toks, f = None):
    g0 = [x for x in filter(f, toks)]
    g1 = (x for x in g0)
    g1.next()
    for i in zip(g0, g1):
        yield i

def dropGarbage (toks):
    for t in toks:
        yield ''.join(filter(lambda x : x not in '<>\'",();', t))

class Token :

    def __init__ (self, tid):
        self.tid = tid
        self.start = set()
        self.part = set()

    def addPart (self, n):
        self.part.add(n)

    def addStart (self, s):
        self.start.add(s)

    def isStart (self):
        return len(self.start) > 0

    def __hash__ (self):
        return hash(self.tid)

    def __cmp__ (self, x):
        try:
            return cmp(self.tid, x.tid)
        except:
            return cmp(self.tid, x)

class NameTranslator :

    def __init__ (self):
        self.names = dict()
        self.incid = 0

    def subscribe(self,tok,rowid, start=False):
        trs = self.names.get(tok)
        if trs == None:
            self.names[tok] = trs = Token(self.incid)
            self.incid+=1
        if start:
            trs.addStart(rowid)
        else:
            trs.addPart(rowid)

    def __contains__(self, t)
        return t in self.names

    def get(self,t)
        return self.names.get(t)

class Links :

    def __init__ (self):
        self.links = dict()

    def getLinks (self, x):
        lks = self.links
        ret = lks.get(x)
        if ret is None:
            ret = lks[x] = set()
        return ret

    def link (self, x, y):
        self.getLinks(x).add(y)

class TokenGraph :

    def __init__ (self, f = None):
        self.links = Links()
        self.transl = NameTranslator()
        self.filter = f
        self.count=0

    def addRow (self, row):
        toks = row.split()
        toks_cf = (t for t in dropGarbage(toks))
        links, transl = self.links, self.transl
        for i, (nx, ny) in enumerate(buildCouples(toks_cf, self.filter)):
            transl.subscribe(nx, self.count, not i)
            transl.subscribe(ny, self.count)
            links.link(transl.get(nx).tid, transl.get(ny).tid)
        self.count+=1

    def followPath (self,stream):
        lsttoks=(x for x in stream)
        links, transl = self.links, self.transl

        firsttok = lsttoks.next()
        ret = [firsttok]
        head = transl.get(firsttok)
        track = set(head.start)
        for nx in lsttoks:
            nxtok=tansl.get(nx)
            if not nxtok.tid in links.getLinks(head.tid):
                break

            track.intersection_update(lstnx.part)
            if len(track)==0:
                break
            head=lstnx
            ret.append(nx)
        return ret

    def match (self, phrase):
        ret = list()
        stream = list(dropGarbage(phrase))
            for i,t in enumerate(stream):
                tok=transl.get(t)
                if tok and tok.isStart():
                    ret.append(followPath(stream[i:]))
        return ret