Find the shortest whole repetitive substring I'm working on a problem to find wholly repeated shortest substring of a given string, and if no match, return length of the string.

My major idea is using a Trie tree to build substrings from length 1 to half length of the whole string, then traverse the Trie tree to find if there is a wholly repetitive match or not (since when I build Trie tree, I record the depth of leaf node and also how many times the leaf node has been reached).

I think my algorithm is still \$O(n^2)\$ and I'm looking for any code review comments for my current code and better ideas to improve time complexity.

Input and output example

catcatcat =&gt; 3
aaaaaa=&gt;1
aaaaaba = &gt; 7


My code

from __future__ import print_function
from collections import defaultdict
import sys
class TrieNode:
    def __init__(self):
        self.isEnd = False
        self.children = defaultdict(TrieNode)
        self.count = 0 # reached how many times
        self.depth = 0 # reached by how long sub-string
    def addNode(self, word):
        if not word:
            return
        node = self
        depth = 0
        for ch in word:
            node = node.children[ch]
        node.isEnd = True
        node.count += 1
        node.depth = len(word)
    # return minimal length of whole repetitive match
    # in a recursive way
    def traverseNode(self, totalLen):
        if self.isEnd == True:
            if (self.count * self.depth == totalLen):
                return self.depth
            else:
                return totalLen
        result = sys.maxint # set to a very big value
        for node in self.children.values():
            result = min(node.traverseNode(totalLen), result)

        return result
if __name__ == "__main__":
    results = []
    word = 'catcatcatcat' # output 3
    #word = 'aaaaaa' # output 1
    #word = 'aaaaaab' # output 7
    for step in range(1, len(word)//2 + 1):
        # whole repetive string must be start from zero
        i = 0
        root = TrieNode()
        while i+step &lt;= len(word):
            root.addNode(word[i:i+step])
            i += step
        results.append(root.traverseNode(len(word)))
        print (step, results[-1])

    print (min(results))
Why not use a regular expression?

&gt;&gt;&gt; import re
&gt;&gt;&gt; len(re.match(r'(.+?)\1*$', 'catcatcat').group(1))
3


This has runtime \$Θ(n^2)\$, same as the code in the post, but it's a lot shorter.