International Coding Procedures Company (ICPC) writes all its code in Jedi Script (JS) programming language. JS does not get compiled, but is delivered for execution in its source form. Sources contain comments, extra whitespace (including trailing and leading spaces), and other non-essential features that make them quite large but do not contribute to the semantics of the code, so the process of minification is performed on source files before their delivery to execution to compress sources while preserving their semantics.

You are hired by ICPC to write JS minifier for ICPC. Fortunately, ICPC adheres to very strict programming practices and their JS sources are quite restricted in grammar. They work only on integer algorithms and do not use floating point numbers and strings. 

Every JS source contains a sequence of lines. Each line contains zero or more tokens that can be separated by spaces. On each line, a part of the line that starts with a hash character ('#' code 35), including the hash character itself, is treated as a comment and is ignored up to the end of the line.

Each line is parsed into a sequence of tokens from left to right by repeatedly skipping spaces and finding the longest possible token starting at the current parsing position, thus transforming the source code into a sequence of tokens. All the possible tokens are listed below:  A reserved token is any kind of operator, separator, literal, reserved word, or a name of a library function that should be preserved during the minification process. Reserved tokens are fixed strings of non-space ASCII characters that do not contain the hash character ('#' code 35). All reserved tokens are given as an input to the minification process.  A number token consists of a sequence of digits, where a digit is a character from zero ('0') to nine ('9') inclusive.  A word token consists of a sequence of characters from the following set: lowercase letters, uppercase letters, digits, underscore ('_' code 95), and dollar sign ('$' code 36). A word does not start with a digit. 

Note, that during parsing the longest sequence of characters that satisfies either a number or a word definition, but that appears in the list of reserved tokens, is considered to be a reserved token instead.

During the minification process words are renamed in a systematic fashion using the following algorithm:  Take a list of words that consist only of lowercase letters ordered first by their length, then lexicographically: "a", "b", ..., "z", "aa", "ab", ..., excluding reserved tokens, since they are not considered to be words. This is the target word list.  Rename the first word encountered in the input token sequence to the first word in the target word list and all further occurrences of the same word in the input token sequence, too. Rename the second new word encountered in the input token sequence to the second word in the target word list, and so on. 

The goal of the minification process is to convert the given source to the shortest possible line (counting spaces) that still parses to the same sequence of tokens with the correspondingly renamed words using these JS parsing rules. 


-----Input-----

The first line of the input contains a single integer $n$ ($0 \le n \le 40$) — the number of reserved tokens.

The second line of the input contains the list of reserved tokens separated by spaces without repetitions in the list. Each reserved token is at least one and at most 20 characters long and contains only characters with ASCII codes from 33 (exclamation mark) to 126 (tilde) inclusive, with exception of a hash character ('#' code 35).

The third line of the input contains a single integer $m$ ($1 \le m \le 40$) — the number of lines in the input source code.

Next $m$ lines contain the input source, each source line is at most 80 characters long (counting leading and trailing spaces). Each line contains only characters with ASCII codes from 32 (space) to 126 (tilde) inclusive. The source code is valid and fully parses into a sequence of tokens.


-----Output-----

Write to the output a single line that is the result of the minification process on the input source code. The output source line shall parse to the same sequence of tokens as the input source with the correspondingly renamed words and shall contain the minimum possible number of spaces needed for that. If there are multiple ways to insert the minimum possible number of spaces into the output, use any way. 


-----Examples-----
Input
16
fun while return var { } ( ) , ; > = + ++ - --
9
fun fib(num) { # compute fibs
  var return_value = 1, prev = 0, temp;
  while (num > 0) {
    temp = return_value; return_value = return_value + prev;
    prev = temp;
    num--;
  }
  return return_value;
}

Output
fun a(b){var c=1,d=0,e;while(b>0){e=c;c=c+d;d=e;b--;}return c;}

Input
10
( ) + ++ : -> >> >>: b c)
2
($val1++ + +4 kb) >> :out
b-> + 10 >>: t # using >>: 

Output
(a+++ +4c )>> :d b->+10>>:e

Source: codeforces | Difficulty: VERY_HARD
Tags: Implementation

Greedy algorithms


Solutions:
from collections import defaultdict
n = int(input())
reserved = set(input().split())
m = int(input())
lines = [input().split('#')[0].split() for _ in range(m)]
tokens = sum(lines, [])

def isword(t):
	return not t[0].isdigit() and all((c.isalnum() or c == '_' or c == '$' for c in t))

def ok(t):
	return t in reserved or t.isdigit() or isword(t)

def tokenize(t):
	res = []
	i = 0
	n = len(t)
	while i < n:
		for j in range(n, i, -1):
			if ok(t[i:j]):
				res.append(t[i:j])
				i = j
				break
	return res
tokens = sum(map(tokenize, tokens), [])
dig = 1
k = 0
limit = 26

def next_token():
	global dig, k, limit
	if k == limit:
		k = 0
		dig += 1
		limit = 26 ** dig
	w = []
	l = k
	for _ in range(dig):
		w += chr(ord('a') + l % 26)
		l //= 26
	w = ''.join(reversed(w))
	k += 1
	if w in reserved:
		return next_token()
	return w
dc = defaultdict(next_token)

def replace(t):
	if t in reserved or t.isdigit():
		return t
	return dc[t]

def can_append(a, b, bg):
	if len(a) == 0:
		return True
	for (i, s) in enumerate(bg):
		if i + 1 != len(bg) and len(a) - s > 21:
			continue
		for i in range(len(b)):
			if ok(a[s:] + b[:i + 1]):
				return False
	return True
res = ['']
begin = []
for t in map(replace, tokens):
	if not can_append(res[-1], t, begin):
		res.append('')
		begin = []
	begin.append(len(res[-1]))
	res[-1] += t
print(' '.join(res))


def main():
	t = int(input())
	reserved = set(input().split())
	lines = int(input())
	code = ''
	for i in range(lines):
		code += input() + '\n'

	def is_word(suspect):
		if suspect[0].isdigit():
			return False
		for x in suspect:
			if not x.isalpha() and (not x in {'_', '$'}) and (not x.isdigit()):
				return False
		return True

	def is_token(suspect):
		if suspect in reserved:
			return True
		if is_word(suspect):
			return True
		if suspect.isdigit():
			return True
		return False

	def remove_comments(code):
		rez = ''
		state = None
		for i in range(len(code)):
			if code[i] == '#':
				state = 'comment'
			elif code[i] == '\n':
				rez += code[i]
				state = None
			elif state != 'comment':
				rez += code[i]
		return rez
	code = remove_comments(code)
	code = code.replace('\n', ' ')

	def split(code):
		tokens = []
		i = 0
		while i < len(code):
			if code[i] == ' ':
				i += 1
				continue
			for l in range(min(len(code), 90), 0, -1):
				if is_token(code[i:i + l]):
					tokens.append(code[i:i + l])
					i += l
					break
			else:
				return []
		return tokens

	def minmize(tokens):
		all = []
		pref = [chr(i + ord('a')) for i in range(26)]
		all.extend(pref)
		for ext in range(3):
			cur = []
			for i in range(26):
				for p in pref:
					cur.append(p + chr(i + ord('a')))
			cur.sort()
			all.extend(cur)
			pref = cur[:]
		all.reverse()
		zip = dict()
		for i in range(len(tokens)):
			if not tokens[i] in reserved and (not tokens[i][0].isdigit()):
				if not zip.get(tokens[i], None):
					while all[-1] in reserved:
						all.pop()
					zip[tokens[i]] = all[-1]
					all.pop()
				tokens[i] = zip[tokens[i]]
		return tokens
	tokens = minmize(split(code))

	def cmp(a, b):
		if len(a) != len(b):
			return False
		for i in range(len(a)):
			if a[i] != b[i]:
				return False
		return True
	final = []
	for i in range(len(tokens)):
		p = 0
		for j in range(i - 1, -1, -1):
			if len(''.join(tokens[j:i + 1])) > 23:
				p = j
				break
		st = ''
		if i and (not cmp(tokens[p:i + 1], split(''.join(final[p:i]) + tokens[i]))):
			st += ' '
		final.append(st + tokens[i])
	print(''.join(final))
main()


input()
reserved = input().split(' ')
lines = int(input())
numbers = '0123456789'
let = 'qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890_$'

def wytnij_res(slowo):
	r = ''
	for res in reserved:
		if len(res) > len(r) and slowo.startswith(res):
			r = res
	return r

def wytnij_num(slowo):
	nm = ''
	for c in slowo:
		if c in numbers:
			nm += c
		else:
			break
	return nm

def wytnij_word(slowo):
	nm = ''
	if slowo[0] in numbers:
		return ''
	for c in slowo:
		if c in let:
			nm += c
		else:
			break
	return nm

def wytnij(slowo):
	rs = wytnij_res(slowo)
	nm = wytnij_num(slowo)
	wrd = wytnij_word(slowo)
	ret = ''
	for r in [rs, nm, wrd]:
		if len(r) > len(ret):
			ret = r
	if ret == '':
		print([rs, nm, wrd])
		print(slowo)
		assert False
	return ret
prog = []
for _ in range(lines):
	line = input()
	line = line.split('#')[0]
	line = line.split(' ')
	for l in line:
		while len(l) > 0:
			wrd = wytnij(l)
			l = l[len(wrd):]
			prog.append(wrd)
letters = 'abcdefghijklmnopqrstuvwxyz'

def gen(st):
	ln = len(letters)
	res = []
	for i in range(ln ** st):
		j = i
		if st == 1:
			res.append(letters[i])
		else:
			res.append(letters[i // ln] + letters[i % ln])
	return res
toks = gen(1) + gen(2)
toks = [t for t in toks if t not in reserved]
dct = {}
tprog = []
for p in prog:
	if p not in reserved and p[0] not in numbers:
		if p not in dct:
			dct[p] = toks[0]
			toks = toks[1:]
		p = dct[p]
	tprog.append(p)
res = ''
for tok in reversed(tprog):
	nres = tok + res
	if wytnij(nres) != tok:
		res = tok + ' ' + res
	else:
		res = tok + res
print(res)


import sys
(n, reserved, m, *lines) = sys.stdin.readlines()
n = int(n)
reserved = set(reserved.split())
m = int(m)

def strip_comment(line):
	return line[:-1].split('#', maxsplit=1)[0]
lines = ' '.join(map(strip_comment, lines))

def is_digit(c):
	return '0' <= c <= '9'

def is_word_char(c):
	return c == '_' or c == '$' or '0' <= c <= '9' or ('A' <= c <= 'Z') or ('a' <= c <= 'z')

def digit_match(s, ind):
	assert ind < len(s)
	res = 0
	while res + ind < len(s) and is_digit(s[res + ind]):
		res += 1
	return res

def word_match(s, ind):
	assert ind < len(s)
	if is_digit(s[ind]):
		return 0
	res = 0
	while res + ind < len(s) and is_word_char(s[res + ind]):
		res += 1
	return res

def reserved_match(s, ind):
	assert ind < len(s)
	return max((len(r) for r in reserved if s.startswith(r, ind)), default=0)

def tokenize(s):
	ind = 0
	while ind < len(s):
		if s[ind] == ' ':
			ind += 1
			continue
		l = max(digit_match(s, ind), word_match(s, ind), reserved_match(s, ind))
		if l == 0:
			yield '\x00'
			return
		yield s[ind:ind + l]
		ind += l

def simplify_tokens(tokens):

	def lex_next(s):
		for i in range(len(s) - 1, -1, -1):
			assert 'a' <= s[i] <= 'z'
			if s[i] < 'z':
				return s[:i] + chr(ord(s[i]) + 1) + 'a' * (len(s) - i - 1)
		return 'a' * (len(s) + 1)
	converted = {}
	cur_word = ''
	for token in tokens:
		if token in reserved:
			yield token
		elif '0' <= token[0] <= '9':
			yield token
		elif token in converted:
			yield converted[token]
		else:
			cur_word = lex_next(cur_word)
			while cur_word in reserved:
				cur_word = lex_next(cur_word)
			converted[token] = cur_word
			yield cur_word
tokens = list(simplify_tokens(tokenize(lines)))
cur_tokens = []
result = []
for token in tokens:
	cur_tokens.append(token)
	if list(tokenize(''.join(cur_tokens[-21:]))) != cur_tokens[-21:]:
		result.append(''.join(cur_tokens[:-1]))
		cur_tokens = [token]
if cur_tokens:
	result.append(''.join(cur_tokens))
print(' '.join(result))