Terio
BAN USERThe longest path has to be rooted in one node and it is the concatenation of the longest path on the left, the node, and the longest path on the right. For each node, find the longest path rooted on it and find the max of all.
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
class LongestPathFinder:
def check_if_longest(self, key, l_path, r_path):
if len(l_path) + len(r_path) + 1 > self.longest_path_len:
self.longest_path_len = len(l_path) + len(r_path) + 1
self.longest_path_root = key
self.left_deepest_path = l_path
self.right_deepest_path = r_path
def find_deepest_path(self,node):
if node == None:
return []
left_deepest_path = self.find_deepest_path(node.left)
right_deepest_path = self.find_deepest_path(node.right)
self.check_if_longest(node.key, left_deepest_path, right_deepest_path)
if len(left_deepest_path) >= len(right_deepest_path):
return left_deepest_path + [node.key]
else:
return right_deepest_path + [node.key]
def __init__(self,root):
self.longest_path_root = None
self.left_deepest_path = []
self.right_deepest_path = []
self.longest_path_len = 0
self.find_deepest_path(root)
if self.longest_path_len == 0:
self.longest_path = []
else:
self.longest_path = self.left_deepest_path + \
[self.longest_path_root] + \
list(reversed(self.right_deepest_path))
Use the Knuth-Morris-Pratt (KMP) algorithm to find the result. It is implicit in the computation of the failure function, no need to apply the pattern to itself.
def search_greatest_substr_kmp(pattern):
l = len(pattern)
f = [0] * l
j = 0
i = 1
while i < l:
if pattern[i] > pattern[j]:
# Found a substring that is greater than the prefix itself.
# Take the rest of the string
return pattern[i - j:]
elif pattern[i] == pattern[j]:
# There is match, the suffix matched grows by one
f[i] = f[i - 1] + 1
i += 1
j += 1
elif j > 0:
# Try matching with a smaller feasible suffix
j = f[j - 1]
else:
f[i] = 0
i += 1
return f
I like this solution but the code and run time can be reduced in half.
When you are calculating the failure function, you are already applying the pattern to itself. All you need to do is return from the failure function computation as soon as you find a character in the pattern that is greater than the corresponding one in the prefix. There is no need to apply the pattern to itself again in the second half of the code.
There is a simple way of doing this. Get the first node and concatenate to it the rest of the list but with the last node first. Then skip one node and repeat.
- Terio December 11, 2016