This is a continued improvement from discussion here (Find the shortest whole repetitive substring), since code has changed a lot dues to improvement, I post it here. Major smart ideas are from arvindpdmn.
Major algorithm ideas,
- since we need to find wholly repetitive sub-strings, we only build Trie tree if the sub-string length is a factor of total string length (if not a factor, such sub-string are not eligible dues to not able to wholly repetitive)
- If wholly repetitive, all nodes need to have only one child node. I did the checking in method
Trie tree is the best way I can think of to resolve this problem for the purpose of reducing algorithm time complexity, not sure if any other better ideas to make it even faster (in terms of algorithm time complexity perspective).
from __future__ import print_function from collections import defaultdict class TrieNode: def __init__(self): self.children = defaultdict(TrieNode) self.isEnd = False def addNode(self, word): node = self for ch in word: node = node.children[ch] node.isEnd = True def checkChildNumber(self): node = self while node.isEnd == False: if len(node.children) != 1: return False for child in node.children.values(): node = child return True if __name__ == "__main__": word = "catcatcat" # output is 3 #word = "aaaaaaa" # output is 1 #word = "aaaaaab" # output is 7 result = len(word) for subLength in range(1, len(word)//2 + 1): if len(word) % subLength == 0: start = 0 root = TrieNode() while start <= len(word) - subLength: root.addNode(word[start:start+subLength]) start += subLength if root.checkChildNumber(): result = min(result, subLength) print (result)