kobra_stave.py

# coding=utf-8
# Kobra lærer å stave av Sigurd Fosseng
def main():
    from sys import stdin
    s = raw_input().split()
    queries = stdin.read()
    word_tree = {'':{}}
    word_places = {}
    sted = 0
    if '?' in queries:
        for w in s:
            l = len(w)
            try:
                word_places[w].append(sted)
            except: #betyr at vi ikke har ordet fra før. add, and split
                word_places[w] = [sted]
                bigger_part=w
                for x in xrange(l-1,0,-1): 
                    smaller_part=w[:x] 
                    try:
                        word_tree[smaller_part][bigger_part]=None
                    except: 
                        word_tree[smaller_part] = {bigger_part:None}
                    bigger_part = smaller_part
    
                word_tree[''][bigger_part] = None
            sted += l+1       
    else: #ikke ?, vanlig dict.
        for w in s:
            try:
                word_places[w].append(sted)
            except:
                word_places[w] = [sted]
            sted += len(w)+1

    qmem = {} #husk svar fra tidligere queries
    for q in queries.split():
        #print
        #print "søker etter \""+q+"\""
        try:
            print qmem[q]
        except:
            if "?" in q:
                query_split = q.split("?")

                try: 
                    a = word_tree[query_split[0]] #stack
                except: 
                    a = []
                #print "init stack:", a
                
                for x in query_split[1:-1]:
                    #skjer hvis det er flere ?
                    tmp = []
                    for y in a:
                        try: 
                            tmp.extend(word_tree[y+x])
                            #print "la til:", ", ".join(word_tree[y+x])
                        except: 
                            pass
                    a=tmp #ny stack
                    #print "ny stack",a

                #finn posisjoner
                positions = []
                rest = query_split[-1]
                #print "loop, finner stack[i]+resten:"
                for x in a:
                    try:
                        #print " "+x+rest
                        positions.extend(word_places[x+rest])
                    except: 
                        pass
                positions.sort() # det er litt random rekkefolge
                
                svar = ": ".join((q," ".join(map(str, positions)))) #kjappere
            else:
                try:
                    wp = word_places[q]
                    svar= ": ".join((q," ".join(map(str,wp))))
                except:
                    svar = q+":"
            qmem[q] = svar
            print svar
main()