# Adrian deWynter, 2017
# Implementation of various algorithms
# applied to strings

# Given a long string find the greater
# number that is also a palindrome.
def nextPalindrome(S):

	def isPalindrome(x): return x == x[::-1]

	while True:
		S = S + 1
		if isPalindrome(S): return S


# Given two words A,B find if A = rot(B)
def isRotation(A,B):
	



# Print all possible combinations of a certain
# s \in {0,1}^* for a given wildcard (*)
def wS(s,i):

	if i == len(s):
		print "".join(s)
	else:
		if s[i] == "*":
			s[i] = "1"
			wS(s,i+1)
			s[i] = "0"
			wS(s,i+1)
		else:
			wS(s,i+1)


def allNonRepeatingWordsInTwoSentences(a,b):

	# Hash a, hash b, print differences. O(a + b)
	d = {}

	def insertHash(x):
		if x not in d:
			d[x] = 1
		else:
			d[x] = d[x] + 1

	for c in a:
		insertHash(c.split(" "))
	for c in b:
		insertHash(c.split(" "))

	ans = []
	for k,v in d:
		if d[k] > 1:
			ans.append(d[k])
			ans.append(" ")

	print "".join(ans[:-1])


# Split a string into the minimum number of substrings
# such that each substring is a palindrome.
# This doesn't really work.
# Instead maintain an array:
# 	mincuts[i] = min cuts until i in S
#	ispalindrome[i][j]
def minSubPalindromes(S):

	p = []
	M = [[None for _ in range(len(S))] for _ in range(len(S))]

	for i in range(1,len(S)):
		for i in range(1,len(S)):

			if S[i] == S[j]:
				M[i][j] = max(M[i-1][j-1], M[i-1][j], M[i][j - 1]) + 1
			else:
				M[i][j] = max(M[i-1][j-1], M[i-1][j], M[i][j - 1]) + 1

	print M[-1][-1]


# Longest word made of words.
# I have no idea what it does.
def longestWordsMadeOfWords(W):

	# First method
	W.sort()
	W=W[::-1]
	i = 0

	def splitWord(w):
		ans = []
		for i in range(1,len(w)):
			ans.append( (w[:i], w[i:] ))
		return ans

	while i < len(W):
		w = W[i]
		for a,b in splitWord(w):
			if a not in W or b not in W:
				i = i + 1
				break
	return w


# Find smallest window if a string A containing all
# characters of another string B
def smallestWindow(A,B):

	M = [[0 for _ in range(len(A))] for _ in range(len(B))]

	M[0] = [1 if B[0] == A[i] else 0 for i in range(len(A))]
	for i in range(len(B)): M[i][0] = 1 if A[0] ==  B[i] else 0

	for i in range(1,len(A)):
		for j in range(1,len(B)):
			if A[i] == A[j]:
				M[i][j] = max(1, M[i-1][j-1],M[i-1][j],M[i][j-1])

	if M[-1][-1] == len(B): return 1


# Alphabetical order:
def alienAlphabet(A):

	node = None
	
	def insertNode(node,v):		
		node_ = Node()
		node_.value = v
		node_.next = None
		node.next = node_

	for k,v in A:
		node = Node()
		node.value = k[0]
		for c in range(1,len(k)):
			if node.value != k[c]:
				node_ = node
				while node.next is not None:
					if node.value == k[c]:
						break
					else:
						if node.next.value != k[c]:
							insertNode(node,k[c])
					node = node.next

			if node.next is None and node.value != k[c]:
				insertNode(node,k[c])

	while node.next is not None: print node.value


# Find minimum nnumber of operations that can
# be performed to turn s1 into s2
def minNum(s1,s2):
	
	def levensheinDistance(s1,s2,ls1=len(s1),ls2=len(s2)):
		
		if ls1 == 0: return ls2
		if ls2 == 0: return ls1
		if s1[ls1-1] == s2[ls2-1]:
			cost = 0
		else:
			cost = 1
		return min(
			levensheinDistance(s1,s2,ls1-1,ls2) + 1,
			levensheinDistance(s1,s2,ls1,ls2-1) + 1,
			levensheinDistance(s1,s2,ls1-1,ls2-1) + cost)
		

	return levensheinDistance(s1,s2)

	# Dynamic programming approach:
	M = [[0 for _ in s1] for _ in s2]

	for i in range(1,len(s1)):
		for j in range(1,len(s2)):
			if s1[i] != s2[j]:
				M[i][j] = max(M[i-1][j],M[i][j-1],M[i-1][j-1])

	print M[-1][-1]

# Find all positions where the anagram of a substring
# S exists in A
# Complexity: O(A + S)
def needleHaystack(S,A):

	indexes = []
	T = sufixTree(A)

	i = 0

	while i < len(S):
		k = T.findSubstring(S)
		if k = len(S): indexes.append(k)
		S = getNextAnagram(S)
	return indexes

	left,right = 0,0
	count = len(S)
	indexes = []

	dic = {}

	for c in S:
		if c in S:
			dic[c] =  dic[c] + 1
		else:
			dic[c] = 0

	while right < len(A):

		right = right + 1

		if A[right] in dic and A[right] >= 0:
			A[right] = A[right] - 1
			count = count -1

		if count == 0: indexes.append(left)

		left = left + 1

		if right - left == len(S) and left in A and A[left] >= 0:
			A[left] = A[left] + 1
			count = count + 1

	return indexes

return B in A+A