Read problems statements in Mandarin Chinese and Russian as well. 

Given n words w[1..n], which originate from the same stem (e.g. grace, graceful, disgraceful, gracefully), we are interested in the original stem. To simplify the problem, we define the stem as the longest consecutive substring that occurs in all the n words. If there are ties, we will choose the smallest one in the alphabetical (lexicographic) order.

------ Input ------ 

The first line contains an integer T denoting the total number of test cases.
In each test cases, the first line contains an integer n denoting the number of words. In the second line, n words w[1..n] consisting of lower case characters are given as a single space-spearated list.

------ Output ------ 

For each test case, output the stem in a new line.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ n ≤ 10$
$1 ≤ |w[i]| ≤ 20$

----- Sample Input 1 ------ 
1
4
grace graceful disgraceful gracefully
----- Sample Output 1 ------ 
grace
----- explanation 1 ------ 
The stem is grace.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
def producesubstrings(s, x):
	subs = []
	for i in range(0, len(s) - x + 1):
		subs.append(s[i:x + i])
	return subs
t = int(input())
while t:
	answer = []
	t = t - 1
	n = int(input())
	s = input()
	list = s.split()
	min = len(list[0])
	smalleststring = list[0]
	smallstrings = []
	for s in list:
		if len(s) < min:
			min = len(s)
			smalleststring = s
	for s in list:
		if len(s) == len(smalleststring):
			smallstrings.append(s)
	for ss in smallstrings:
		for i in range(len(ss), 0, -1):
			flag = 0
			subs = producesubstrings(ss, i)
			for s in subs:
				flag = 0
				for x in list:
					if not s in x:
						flag = 1
						break
				if flag == 0:
					answer.append(s)
			if flag == 0:
				break
	max = len(answer[0])
	for a in answer:
		if len(a) > max:
			max = len(a)
	answer1 = []
	for a in answer:
		if len(a) == max:
			answer1.append(a)
	answer1.sort()
	print(answer1[0])


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(str, input().split()))
	for i in range(n):
		y = l[i]
		x = list()
		for j in range(len(y)):
			for k in range(j + 1, len(y)):
				x.append(y[j:k + 1])
		if i == 0:
			xl = set(x)
		else:
			ans = set(x)
			xl = xl.intersection(ans)
	xl = list(xl)
	xl.sort()
	a = 0
	s = ''
	for i in xl:
		if len(i) > a:
			a = len(i)
			s = i
	print(s)


import sys
T = int(sys.stdin.readline())
for t in range(T):
	n = int(sys.stdin.readline())
	w = sys.stdin.readline().strip()
	words = w.split()
	shortest_word = min(words, key=len)
	longest_substr_len = 0
	longest_substr = ''
	for i in range(0, len(shortest_word)):
		for j in reversed(range(i + 1, len(shortest_word) + 1)):
			sub_str = shortest_word[i:j]
			found = True
			for word in words:
				if sub_str not in word:
					found = False
					break
			if found:
				if len(sub_str) > longest_substr_len:
					longest_substr_len = len(sub_str)
					longest_substr = sub_str
				elif len(sub_str) == longest_substr_len:
					if sub_str < longest_substr:
						longest_substr_len = len(sub_str)
						longest_substr = sub_str
	print(longest_substr)


T = int(input())
for i in range(T):
	n = int(input())
	(w, l) = ([], [])
	S = input()
	w = S.split()
	for j in w:
		l.append(len(j))
	ppe = w[l.index(min(l))]
	w.remove(ppe)
	(a, b) = (0, len(ppe))
	ppeTemp = ''
	while a != len(ppe):
		test = True
		for k in w:
			if not ppe[a:b] in k:
				test = False
				break
		if test and len(ppe[a:b]) > len(ppeTemp):
			ppeTemp = ppe[a:b]
		elif b != a:
			b = b - 1
		else:
			a = a + 1
			b = len(ppe)
	print(ppeTemp)


t = int(input())
for tt in range(t):
	n = int(input())
	s = input().split()
	r = ''
	for i in range(len(s[0])):
		for j in range(i + 1, len(s[0]) + 1):
			t = s[0][i:j]
			for p in s:
				if p.count(t) == 0:
					t = ''
			if (len(t), r) > (len(r), t):
				r = t
	print(r)


for _ in range(int(input())):
	n = int(input())
	z = input().strip().split()
	w = list(z[:n])
	wlen = [len(aw) for aw in w]
	mlen = min(wlen)
	ref = w[wlen.index(mlen)]
	subs = []
	for pos in range(mlen):
		if all((ref[pos] in aw for aw in w)):
			subs.append(pos)
	if len(subs) == 0:
		print()
		continue
	tlen = 2
	while True:
		nsubs = []
		for pos in subs:
			if pos + 1 in subs:
				if all((ref[pos:pos + tlen] in aw for aw in w)):
					nsubs.append(pos)
		if len(nsubs) == 0:
			break
		subs = nsubs
		tlen += 1
	tlen -= 1
	ans = [ref[pos:pos + tlen] for pos in subs]
	ans.sort()
	print(ans[0])


import sys
t = int(sys.stdin.readline())
for it in range(t):
	n = int(sys.stdin.readline())
	strs = sys.stdin.readline().split(' ')
	strs.sort(key=len)
	start = mxlen = 0
	stop = 1
	mxterm = ''
	while start < len(strs[0]) and stop < len(strs[0]) + 1:
		temp = strs[0][start:stop]
		valid = True
		for ph in strs[1:]:
			if temp not in ph:
				valid = False
				break
		if not valid:
			start += 1
			if stop <= start:
				stop = start + 1
		else:
			if mxlen < len(temp):
				mxlen = len(temp)
				mxterm = temp
			stop += 1
	print(mxterm)


test = int(input())
for i in range(test):
	n = int(input())
	string = input().split(' ')
	string.sort(key=len)
	subst = ''
	for j in range(len(string[0])):
		for k in range(j + 1, len(string[0]) + 1):
			word = string[0][j:k]
			value = True
			for l in string[1:]:
				if word not in l:
					value = False
					break
			if value:
				if len(word) > len(subst):
					subst = word
				elif len(word) == len(subst) and subst > word:
					subst = word
	print(subst)


import math
T = int(input())
for t in range(T):
	n = int(input())
	w = [x for x in input().split()]
	a = max(w, key=len)
	l = len(a)
	candidate = []
	while l > 0:
		i = 0
		while i + l <= len(a):
			if all((a[i:i + l] in s for s in w)):
				candidate.append(a[i:i + l])
				i += 1
			else:
				i += 1
		if not len(candidate) == 0:
			break
		l -= 1
	candidate.sort()
	print(candidate[0])


def check(x, l):
	count = 0
	for i in range(len(l)):
		if x in l[i]:
			count += 1
	return count
for j in range(int(input())):
	n = int(input())
	l = input().split(' ')
	min_len = 30
	index_min = 0
	for i in l:
		if len(i) < min_len:
			min_len = len(i)
			index_min = l.index(i)
	x = l[index_min]
	i = 0
	j = len(x) - 1
	m = n = 0
	p = 0
	while i < len(x):
		j = len(x)
		while j > -1:
			c = check(x[i:j], l)
			if c == len(l):
				if p < len(x[i:j]):
					p = len(x[i:j])
					m = i
					n = j
			j -= 1
		i += 1
	print(x[m:n])


for _ in range(int(input())):
	n = int(input())
	s = [s for s in input().split()]
	s.sort(key=len)
	s1 = s[0]
	l = []
	for i in range(0, len(s1)):
		for j in range(i + 1, len(s1) + 1):
			l.append(s1[i:j])
	ans = ''
	for ele in l:
		for words in s:
			if not ele in words:
				break
		else:
			if len(ele) > len(ans):
				ans = ele
			if len(ele) == len(ans):
				if ele < ans:
					ans = ele
	print(ans)


def rec(L, index, common):
	ans = []
	for i in range(0, len(common)):
		if L[index].find(common[i], 0, len(L[index])) > -1:
			ans.append(common[i])
	return ans
t = int(input())
for deju in range(t):
	L = []
	n = int(input())
	L = input().split()
	if n == 1:
		print(L[0])
		continue
	common = []
	for i in range(0, len(L[0])):
		for j in range(i, len(L[0])):
			if L[1].find(L[0][i:j + 1], 0, len(L[1])) > -1:
				common.append(L[0][i:j + 1])
	for i in range(2, n):
		common = rec(L, i, common)
	maxi = 0
	ans = []
	for i in range(len(common)):
		maxi = max(maxi, len(common[i]))
	for i in range(len(common)):
		if len(common[i]) == maxi:
			ans.append(common[i])
	ans.sort()
	print(ans[0])


from collections import Counter
T = int(input())
for _ in range(T):
	n = int(input())
	u = None
	for w in input().split():
		s = set()
		m = len(w)
		for l in range(m):
			for r in range(l + 1, m + 1):
				s.add(w[l:r])
		if u is None:
			u = s
		else:
			u &= s
	print(max(u, key=lambda s: len(s)))


for t in range(int(input())):
	n = int(input())
	a = list(input().split(' '))
	d = ''
	count = 0
	max = 0
	mx = ''
	for i in range(len(a[0])):
		count = 0
		for k in range(i, len(a[0])):
			d += a[0][k]
			count = 0
			for j in a[1:]:
				if d in j:
					count += 1
			if count == n - 1:
				if len(d) > max:
					max = len(d)
					mx = d
				elif len(d) == max:
					mx = min(d, mx)
		else:
			d = ''
	print(mx)


import sys
T = sys.stdin.readline()
for i in range(int(T)):
	root = ''
	n = sys.stdin.readline()
	words = sys.stdin.readline().split()
	for j in range(len(words[0])):
		for k in range(len(words[0])):
			pot_root = words[0][j:k + 1]
			r = True
			for item in words:
				if pot_root not in item:
					r = False
			if r == True and len(pot_root) >= len(root):
				if len(root) == len(pot_root):
					if pot_root < root:
						root = pot_root
				else:
					root = pot_root
	print(root)


T = int(input())
for t in range(T):
	n = int(input())
	words = input().split()
	L = len(words[0])
	ans = ''
	for i in range(L):
		for j in range(L):
			s = words[0][j:i + 1]
			for word in words:
				if s not in word:
					break
			else:
				if len(s) > len(ans) or (len(s) == len(ans) and s < ans):
					ans = s
	print(ans)


import math
from decimal import *
import sys

def ok(word):
	ans = 1
	l0 = len(word)
	for j in range(1, n):
		fail = 1
		l = len(S[j])
		for k in range(0, l - l0 + 1):
			if S[j][k:k + l0] == word:
				fail = 0
		if fail == 1:
			ans = 0
	return ans
T = int(input())
for i in range(0, T):
	n = int(input())
	S = input().split()
	l0 = len(S[0])
	ml = 0
	L = []
	for j in range(0, l0):
		for k in range(j, l0):
			if ok(S[0][j:k + 1]) == 1:
				L.append(S[0][j:k + 1])
				if len(S[0][j:k + 1]) > ml:
					ml = len(S[0][j:k + 1])
	L2 = []
	for j in L:
		if len(j) == ml:
			L2.append(j)
	L2.sort()
	if len(L2) == 0:
		print()
	else:
		print(L2[0])


def smallest_word(arr, n):
	w = arr[0]
	length = len(arr[0])
	for word in arr:
		if len(word) < length:
			w = word
			length = len(word)
	return w

def solve(arr, n):
	w = smallest_word(arr, n)
	length = 0
	s = ''
	for i in range(0, len(w)):
		for j in range(i + 1, len(w) + 1):
			substring = w[i:j]
			if j - i < length:
				continue
			flag = True
			for word in arr:
				if substring not in word:
					flag = False
					break
			if flag and (j - i > len(s) or (substring < s and len(substring) == len(s))):
				s = substring
	print(s)
t = int(input())
for i in range(t):
	n = int(input())
	arr = input().split()
	solve(arr, n)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(input().split())
	mxl = 0
	mx = ''
	for i in range(len(a[0])):
		st = ''
		for j in range(i, len(a[0])):
			st += a[0][j]
			cnt = 0
			for k in a[1:]:
				if st in k:
					cnt += 1
			if cnt == n - 1:
				if len(st) > mxl:
					mxl = len(st)
					mx = st
				elif len(st) == mxl:
					mx = min(st, mx)
	print(mx)


import sys
import queue
t = int(input())
while t:
	n = int(input())
	line = input().split()
	w = [x for x in line]
	n1 = len(w[0])
	ans = ''
	for size in range(1, n1 + 1):
		for i in range(0, n1 - size + 1):
			flag = True
			for k in range(n):
				if w[0][i:i + size] not in w[k]:
					flag = False
					break
			if flag:
				if ans == '' or size > len(ans):
					ans = w[0][i:i + size]
				elif len(ans) == size:
					if w[0][i:i + size] < ans:
						ans = w[0][i:i + size]
	sys.stdout.write(ans + '\n')
	t -= 1


import sys
T = int(sys.stdin.readline())
for i in range(T):
	n = int(sys.stdin.readline())
	s = sys.stdin.readline().strip()
	a = s.split()
	min_string = min(a, key=len)
	length = 0
	sub_str = ''
	length_sub_str = 0
	longest_sub_str = ''
	for i in range(0, len(min_string)):
		for j in range(i + 1, len(min_string) + 1):
			sub_str = min_string[i:j]
			flag = False
			for ele in a:
				if sub_str in ele:
					flag = True
				else:
					flag = False
					break
			if flag == True:
				if length_sub_str < len(sub_str):
					length_sub_str = len(sub_str)
					longest_sub_str = sub_str
				elif length_sub_str == len(sub_str):
					if longest_sub_str > sub_str:
						longest_sub_str = sub_str
	print(longest_sub_str)