diff options
| author | Mohammad S Anwar <mohammad.anwar@yahoo.com> | 2021-12-28 13:57:10 +0000 |
|---|---|---|
| committer | Mohammad S Anwar <mohammad.anwar@yahoo.com> | 2021-12-28 13:57:10 +0000 |
| commit | 36140e30ca795963deb90ce1f97debf895f52646 (patch) | |
| tree | f311a009a8add826dcaf633b90fcc4fa2ad0cce9 /challenge-145/eric-cheung/python | |
| parent | 80b735486c2e191c8f6974ba7db03d47293338ee (diff) | |
| download | perlweeklychallenge-club-36140e30ca795963deb90ce1f97debf895f52646.tar.gz perlweeklychallenge-club-36140e30ca795963deb90ce1f97debf895f52646.tar.bz2 perlweeklychallenge-club-36140e30ca795963deb90ce1f97debf895f52646.zip | |
- Added guest contributions by Eric Cheung.
Diffstat (limited to 'challenge-145/eric-cheung/python')
| -rwxr-xr-x | challenge-145/eric-cheung/python/ch-2.py | 148 |
1 files changed, 148 insertions, 0 deletions
diff --git a/challenge-145/eric-cheung/python/ch-2.py b/challenge-145/eric-cheung/python/ch-2.py new file mode 100755 index 0000000000..5d4276b2e6 --- /dev/null +++ b/challenge-145/eric-cheung/python/ch-2.py @@ -0,0 +1,148 @@ +import logging
+
+## Credit:
+## https://gist.github.com/shubham2508/9188707973e9a758c0edefe577c0da20
+
+## Remarks:
+## https://stackoverflow.com/questions/2802726/putting-a-simple-if-then-else-statement-on-one-line
+## https://en.wikipedia.org/wiki/%3F:#Python
+
+## Links Used:
+## http://adilet.org/blog/palindromic-tree/
+## https://medium.com/@alessiopiergiacomi/eertree-or-palindromic-tree-82453e75025b
+## It solves the problem in O(n)
+
+class PalindromicNode:
+ def __init__(self, start = 0, end = 0):
+ self.start = start
+ self.end = end
+ self.len = end - start + 1
+ self.insertionEdge = [0] * 26
+ self.suffixLink = None
+
+ ## Optional Attribute
+ self.count = 1 ## Stores number of times this palindrome was repeated
+ self.num_of_suffix_links = 1 ## stores number of suffix link till imaginary node
+
+ def increment_count(self):
+ self.count = self.count + 1
+
+class PalindromicTree:
+ def __init__(self, value):
+ self.emptyNode = PalindromicNode()
+ self.imaginaryNode = PalindromicNode()
+ self.tree = []
+ self.string = value
+ self.total_palindromes = 0
+ self.distinct_palindromes = 0
+ self.emptyNode.suffixLink = self.imaginaryNode
+ self.imaginaryNode.suffixLink = self.imaginaryNode
+ self.imaginaryNode.len = -1
+ self.emptyNode.len = 0
+
+ self.current_suffix = self.imaginaryNode
+
+ def insert_letter(self, curr_ind, character):
+ chr_index = ord(character) - 97
+ new_node = None
+ curr_suffix = self.current_suffix
+
+ if curr_suffix.len > 0:
+ logging.debug(f'\n curr_suffix is : {self.string[curr_suffix.start:curr_suffix.end + 1]}')
+
+ while curr_suffix:
+ curr_start = curr_ind if curr_suffix.len == -1 else curr_ind - curr_suffix.len - 1
+
+ if curr_start >= 0 and self.string[curr_start] == character:
+ if not curr_suffix.insertionEdge[chr_index]:
+ new_node = PalindromicNode(start = curr_start, end = curr_ind)
+ logging.info(f' new_node starts from: {new_node.start} ends at: {new_node.end}')
+ curr_suffix.insertionEdge[chr_index] = new_node
+ self.distinct_palindromes = self.distinct_palindromes + 1
+
+ break
+ else:
+ new_node = curr_suffix.insertionEdge[chr_index]
+ self.total_palindromes = self.total_palindromes + new_node.num_of_suffix_links
+ new_node.increment_count()
+ self.current_suffix = new_node
+ logging.info(f' new_node is already present: {self.string[new_node.start:new_node.end + 1]}')
+ logging.debug(f' Palindromes til now: {self.total_palindromes}')
+
+ return
+
+ curr_suffix = curr_suffix.suffixLink
+
+ self.tree.append(new_node)
+ self.current_suffix = new_node
+
+ if new_node.start == new_node.end:
+ new_node.suffixLink = self.emptyNode
+ self.total_palindromes += new_node.num_of_suffix_links
+ logging.debug(f' Palindromes til now: {self.total_palindromes}')
+ return
+
+ curr_suffix = curr_suffix.suffixLink
+
+ while True:
+ curr_start = curr_ind if curr_suffix.len == -1 else curr_ind - curr_suffix.len - 1
+
+ if curr_start >= 0 and self.string[curr_start] == character:
+ new_node.suffixLink = curr_suffix.insertionEdge[chr_index]
+ new_node.num_of_suffix_links = new_node.num_of_suffix_links + new_node.suffixLink.num_of_suffix_links
+ self.total_palindromes = self.total_palindromes + new_node.num_of_suffix_links
+
+ logging.debug(f' new_node suffix link is : {self.string[new_node.suffixLink.start:new_node.suffixLink.end + 1]}')
+
+ break
+
+ curr_suffix = curr_suffix.suffixLink
+
+ logging.debug(f' Palindromes til now: {self.total_palindromes}')
+
+ def get_number_of_occurrence_of_sub_palindromes(self):
+
+ total_len = len(self.tree)
+
+ for j in range(total_len - 1, -1, -1):
+ self.tree[j].suffixLink.count = self.tree[j].suffixLink.count + self.tree[j].count
+
+ total_palindromes = 0
+
+ for treeNode in self.tree:
+ start, end, count = treeNode.start, treeNode.end, treeNode.count
+ logging.critical(f' Palindrome is {self.string[start:end + 1]} number of times: {count} ')
+ total_palindromes += count
+
+ logging.critical(f' Total number of palindromes: {total_palindromes} ')
+
+
+if __name__ == "__main__":
+
+ ## Example 1:
+ ## string = "redivider"
+
+ ## Example 2:
+ ## string = "deific"
+
+ ## Example 3:
+ ## string = "rotors"
+
+ ## Example 4:
+ ## string = "challenge"
+
+ ## Example 5:
+ ## string = "champion"
+
+ ## Example 6:
+ string = "christmas"
+
+ logging.basicConfig(level = logging.INFO)
+ palindromicTree = PalindromicTree(string)
+ for index, ch in enumerate(string):
+ palindromicTree.insert_letter(index, ch)
+
+ logging.critical(f' Total number of palindromes: {palindromicTree.total_palindromes} ')
+ logging.critical(f' Total number of distinct palindromes: {palindromicTree.distinct_palindromes}')
+
+ palindromicTree.get_number_of_occurrence_of_sub_palindromes()
|