#! /usr/local/bin/python2.4
#
# Copyright (c) 2008 Raimo Niskanen <raimo (dot) niskanen {at} ericsson <dot> com>.
# All rights reserved.
#
# Permission to use, copy, modify, and distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
#
##
## Take a list of unknown users on stdin, store it internally
## in two character trees, one for suffixes and one for
## prefixes. Key length on first level is sys.argv[1],
## on the other levels 1. Prune the trees, that is
## all toplevel branches with a leaf count >= sys.argv[2]
## on the level with half the branch leaf count.
## That all was to get a prefix and a suffix tree.
##
## Now remove all protected users in the file sys.argv[3]
## from the prefix and suffix trees.
## 
## Finally print out the prefix tree keys, prefixed with '^',
## the suffix tree keys suffixed with '$', and all
## unknown users (except for the protected) that does
## not match neither any prefix nor any suffix.
##
## In short, take list of unknown users on stdin
## and print a list of prefix/suffix/exact patterns
## on stdout.
##
#
import sys
import copy

minw  = int(sys.argv[1])  # min chars in prefix/suffix
mink  = int(sys.argv[2])  # min count to follow
fprot = open(sys.argv[3]) # protected users


def printf(format, *args):
    sys.stdout.write(format % args)

# insert string in tree, return True if it was a new string
def insert(t, s, n, i=0):
    if i == 0 and len(s) < n:
	return False
    if i+n > len(s):
	return True
    key = s[i:i+n]
    if not t[0].has_key(key):
	t[0][key] = [{}, 0]
    if insert(t[0][key], s, 1, i+n):
	t[1] = t[1]+1
	return True
    else:
	return False

# delete string from tree, or rather any tree path that is a prefix of string
def delete(t, s, n, i=0):
    if i == 0 and len(s) < n:
	return False
    if i+n > len(s):
	return True
    key = s[i:i+n]
    if t[0].has_key(key):
	if not delete(t[0][key], s, 1, i+n):
	    return False
	t[1] = t[1]-1
	del t[0][key]
    return len(t[0]) == 0

def match(t, s, n, i=0):
    if len(s) < n: return False
    key = s[i:i+n]
    i = i+n
    n = 1
    node = t
    while node[0].has_key(key):
	node = node[0][key]
	if i+n <= len(s):
	    key = s[i:i+n]
	    i = i+n
	else:
	    break
    return len(node[0]) == 0

def prune_n(t, nmin):
    found = True
    for k in t[0].keys():
	v = t[0][k]
	if v[1] >= nmin:
	    found = False
	    if prune_n(v, nmin):
		t[0][k] = [{}, 0]
	else:
	    del(t[0][k])
    return found

def prune(t, n):
    found = True
    for k in t[0].keys():
	v = t[0][k]
	if v[1] >= n:
	    found = False
	    if prune_n(v, max(v[1]/2, 2)):
		t[0][k] = [{}, 0]
	else:
	    del(t[0][k])
    return found

def traverse(t, s=''):
    for k, v in t[0].iteritems():
	if v[0] == {}:
	    yield s+k
	else:
	    for x in traverse(v, s+k):
		yield x

def rtraverse(t, s=''):
    for x in traverse(t, s):
	yield x[::-1]

def dump(t, s=''):
    print s, t[1]
    for k, v in t[0].iteritems():
	dump(v, s+k)



# fill forward and reverse tree with user names
ftree = [{}, 0] # Content, leaf count
rtree = [{}, 0] # Content, leaf count
for line in sys.stdin:
    line = line.rstrip('\n').lower()
    if len(line) == 0: next
    if line[0]   == '^': next
    if line[-1]  == '$': next
    insert(ftree, line, minw)
    insert(rtree, line[::-1], minw)

atree = copy.deepcopy(ftree) # keep for traversal later
# trim all thin branches
prune(ftree, mink)
prune(rtree, mink)

# remove all protected names
protected = set()
for line in fprot:
    line = line.rstrip('\n').lower()
    if len(line) == 0: next
    if line[0]   == '^': next
    if line[-1]  == '$': next
    protected.add(line)
    delete(ftree, line, minw)
    delete(rtree, line[::-1], minw)

# print prefix and suffix patterns
for x in sorted(traverse(ftree)):
    printf("^%s\n", x)
for x in sorted(rtraverse(rtree)):
    printf("%s$\n", x)

# print all names not matched by prefix and suffix patterns,
# except the protected
for x in sorted(traverse(atree)):
    if not (x in protected) and not match(ftree, x, minw) and not match(rtree, x[::-1], minw):
	printf("%s\n", x)