Data Structure and Algorithm Implemented in Python

2016-10-05

• Manacher Algorithm added
• There is also the dynamic programming algorithm and the O(1)-space algorithm to longest palindrome substring (LPS) problem
• Manacher Algorithm is an linear-time and linear-spaced algorithm to find the LPS.
• Test cases are randomly generated by random.choice(char_set), where char_set only contain 5 different character and the length of each test string are set to 300
• The result of Manacher algorithm should be the same as the result from other LPS algorithms

2016-10-04

• KMP algorithm added
• KMP is an O(n) time strStr algorithm even for worst cases
• Test cases are generated from the sample text in Wiki-pedia on Knuth–Morris–Pratt_algorithm
• The result of KMP algorithm should be the same as the result of normal strStr function

2016-09-29

• Fenwick Tree added
• Fenwick Tree is also known as Binary Indexed Tree
• Fenwick Tree is used to calculate contiguous sum of given list. The sum_up operation, update operation would take O(log n) time on average
• Test cases are generated from range(1, 1001)
• According to the test, fenwickTree.get_index(i) should be equal to i+1, while fenwickTree.query_sum(i,j) should be equal to the contiguous sum from i+1 to j+1 inclusively

2016-08-15

• Some basic algorithms in "Data Structure and Algorithm Analysis in C" by Mark Allen Weiss implemented in Python