Find the shortest whole repetitive substring

Question

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 => 3
aaaaaa=>1
aaaaaba = > 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 <= len(word):
            root.addNode(word[i:i+step])
            i += step
        results.append(root.traverseNode(len(word)))
        print (step, results[-1])

    print (min(results))

Answer 1

You don't need a trie: just keep the 'shortest repeating current substring' (which scales as O(n)).

The idea is simple: for each character try to match it to the current shortest string. You will need a pointer to the current character, and one to the current character in the shortest string. Both start at the first character. The shortest string will be that character.

Each time you move to the next character in the main string, try also to move the in current shortest string. If the shortest string is exhausted, i.e. has no more characters, start again at the beginning of the shortest string.

While the characters match, keep going. If the characters do not match, we had a wrong shortest substring and re-initialize it to be the all the characters that we have visited in the main string. Then, reset the pointer in the current shortest string to its beginning and continue.

---

Examples

aaabaaab

• a ← shortest repeating substring is a
• aa ← shortest repeating substring is a
• aaa ← shortest repeating substring is a
• aaab ← shortest repeating substring failed; new shortest repeating substring is aaab
• aaaba ← shortest repeating substring matches (a matches start of aaab
• aaabaa ← shortest repeating substring matches (aa matches start of aaab)
• aaabaaa ← shortest repeating substring matches (aaa matches start of aaab)
• aaabaaab ← shortest repeating substring matches (aaab matches aaab)

No more input, longest repeating substring matched = aaab; length = 4.

aaabaab

• a ← shortest repeating substring is a
• aa ← shortest repeating substring is a
• aaa ← shortest repeating substring is a
• aaab ← shortest repeating substring failed; new shortest repeating substring is aaab
• aaaba ← shortest repeating substring matches
• aaabaa ← shortest repeating substring matches
• aaabaab ← shortest repeating substring no longer matches, so becomes aaabaab. Return 7

Answer 2

I'm not from algorithmic background. Thanks for introducing the trie graph with this question. Below are my comments:

1. Enable PyLint and PEP8 checking in your IDE. This will inform you some basic things about naming conventions, indentation, and so on. For example, addNode() could be renamed as add_node(). Include a blank line between two methods. Include two blank lines above and below class definition.
2. Document your code formally using docstrings. In fact, it would be excellent to use docstrings to describe your algorithm. In its current state, users have to figure out how the code works. Most people will give up and instead come up with their own implementations. Even good open source projects can fail because of poor documentation. If you want others to use your code, write good documentation.
3. Constant sys.maxint is no longer available in Python3. Can change this to make it portable across Python versions. Read this: https://docs.python.org/3.1/whatsnew/3.0.html#integers
4. Your test of 'catcatcatcat' is hard-coded, with couple of other commented test strings. You could improve this by passing test strings from command line. Or you could hard-code a test vectors as a list. Or use doctest that will double up as your unit test.
5. For a string of length n, only sublengths that are factor of n and < n need to be tested. For example with input "catcatcatcat", only sublengths [1, 2, 3, 4, 6] need to be tested. Your code does a test for 5 as well. Test for 12 can be skipped. It's the default answer when smaller sublengths don't work out. This is a small optimization but if your word length is a large prime number, you would save yourself lot of unnecessary computations.
6. Many Python programmers prefer for loops rather than while loops. Use of indices such as i can be removed by refactoring. Use enumerate() built-in function where possible if indices of a list are needed.
7. I found that traverseNode() is not required for this particular problem. What got me thinking was the argument totalLen. Your trie graph/tree must already have knowledge of the total length because you are tracking the count and depth. I then discovered that for this problem, the root must have exactly one direct child. This is enough. At least for this particular problem, is_end, count and depth are redundant.

Code is below:

"""
A module that implements trie search tree.
"""

from __future__ import print_function
from collections import defaultdict
import doctest


class TrieNode:
    """
    Node of a trie search tree.

    Contains as children other trie nodes.
    Each node contains a single character as key.
    Ref: https://en.wikipedia.org/wiki/Trie
    """
    def __init__(self):
        """
        Initialize with empty children.
        """
        self.is_end = False
        self.children = defaultdict(TrieNode)
        self.count = 0 # reached how many times
        self.depth = 0 # reached by how long sub-string

    def add_nodes(self, word):
        """
        Add child nodes recursively.

        First character of input word will be added as a direct child.
        The next character will be a child of the child, and so on.

        Args:
            word (str): Input word to process.
        """
        if not word:
            return
        node = self
        for ch in word:
            node = node.children[ch]
        node.is_end = True
        node.count += 1
        node.depth = len(word)

    @staticmethod
    def whole_shortest_string(word):
        """
        Return the length of the shortest string that spans the entire word.

        >>> TrieNode.whole_shortest_string('catcatcatcat')
        3
        >>> TrieNode.whole_shortest_string('aaaaaa')
        1
        >>> TrieNode.whole_shortest_string('aaaaaba')
        7
        """
        results = [len(word)]
        factors = (x for x in range(1, len(word)) if not len(word)%x)
        for sublen in factors:
            root = TrieNode()
            for subword in (word[x:x+sublen] for x in range(0, len(word), sublen)):
                root.add_nodes(subword)
            if len(root.children) == 1:
                results.append(sublen)
        return min(results)


if __name__ == "__main__":
    doctest.testmod()

Answer 3

Why not use a regular expression?

>>> import re
>>> 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.

Answer 4

This is a variation (perhaps improvement) of my earlier answer. Here, we can construct the tree and then obtain relevant tree information via its various methods. The output from running it is shown at the end.

"""
A module that implements trie search tree.
"""

from __future__ import print_function
from collections import defaultdict
import doctest


class TrieNode:
    """
    Node of a trie search tree.

    Contains as children other trie nodes.
    Each node contains a single character as key.
    Ref: https://en.wikipedia.org/wiki/Trie
    """
    def __init__(self):
        """
        Initialize with empty children.
        """
        self.is_end = False
        self.children = defaultdict(TrieNode)
        self.count = 0 # reached how many times
        self.depth = 0 # reached by how long sub-string

    def add_nodes(self, word):
        """
        Add child nodes recursively.

        First character of input word will be added as a direct child.
        The next character will be a child of the child, and so on.

        Args:
            word (str): Input word to process.
        """
        if not word:
            return
        node = self
        for char in word:
            node = node.children[char]
        node.is_end = True
        node.count += 1
        node.depth = len(word)

    def make_tree(self, words):
        """
        Make a complete trie tree from the list of input words.
        """
        for word in words:
            self.add_nodes(word)

    def total_length(self):
        """
        Return the total length of node and children.

        Returns:
            length (int): Zero for an empty tree.
                        Positive integer otherwise.
        """
        length = 0

        for child in self.children.values():
            length += child.total_length()

        if self.is_end:
            length += self.count * self.depth

        return length

    def num_words(self, uniq=False):
        """
        Get the number of words.

        A word is represented by its endpoint. Multiple occurences are counted
        multiple times, unless uniq argument is set to True.

        Args:
            uniq (bool): If True, counts only unique word occurences.

        Returns:
            cnt (int): Zero for an empty tree.
                    Positive integer otherwise.
        """
        cnt = 0

        for child in self.children.values():
            cnt += child.num_words(uniq)

        if self.is_end:
            if uniq:
                cnt += 1
            else:
                cnt += self.count

        return cnt

    def max_depth(self):
        """
        Get the maximum depth.

        Returns:
            depth (int): Zero for an empty tree.
                        Positive integer otherwise.
        """
        depth = 0

        for child in self.children.values():
            depth = max(depth, child.max_depth())

        if self.is_end:
            return self.depth
        else:
            return depth

    def word_freq(self, prefix=''):
        """
        Get the words and number of occurences.

        Returns:
            wfreq (dict): Keys are words, values are number of occurences.
        """
        wfreq = {}

        for char, child in self.children.items():
            wfreq.update(child.word_freq(prefix+char))

        if self.is_end and prefix:
            wfreq[prefix] = self.count

        return wfreq

    def tree_info(self):
        """
        Get relevant info on the current tree.

        Returns:
            info (dict): Information about the tree.
        """
        info = {
            'total_length' : self.total_length(),
            'num_words' : self.num_words(),
            'num_uniq_words' : self.num_words(uniq=True),
            'max_depth' : self.max_depth(),
            'word_freq' : self.word_freq()
        }
        return info


if __name__ == "__main__":
    test_strs = ["abcabcabb", "catcatcatcat", "aaaaaa", "aaaaaba"]

    for ts in test_strs:
        print("Input: {:s}".format(ts))

        trees = []

        # Create all possible trees
        factors = (x for x in range(1, len(ts)) if not len(ts)%x)
        for sublen in factors:
            # Make the trie tree
            subwords = (ts[x:x+sublen] for x in range(0, len(ts), sublen))
            root = TrieNode()
            root.make_tree(subwords)
            trees.append(root)

        # Find length of shortest whole repetitive substring
        depths = [len(ts)]
        depths += (tree.max_depth() for tree in trees if tree.num_words(uniq=True) == 1)
        print("    Length of shortest whole repetitive substring: {:d}".format(min(depths)))

        # Print each tree's info
        for tree in trees:
            print("    Tree info: {}".format(tree.tree_info()))

Here's the output:

Input: abcabcabb
    Length of shortest whole repetitive substring: 9
    Tree info: {'word_freq': {'c': 2, 'b': 4, 'a': 3}, 'total_length': 9, 'max_depth': 1, 'num_words': 9, 'num_uniq_words': 3}
    Tree info: {'word_freq': {'abb': 1, 'abc': 2}, 'total_length': 9, 'max_depth': 3, 'num_words': 3, 'num_uniq_words': 2}
Input: catcatcatcat
    Length of shortest whole repetitive substring: 3
    Tree info: {'num_words': 12, 'word_freq': {'c': 4, 't': 4, 'a': 4}, 'max_depth': 1, 'num_uniq_words': 3, 'total_length': 12}
    Tree info: {'num_words': 6, 'word_freq': {'ca': 2, 'at': 2, 'tc': 2}, 'max_depth': 2, 'num_uniq_words': 3, 'total_length': 12}
    Tree info: {'num_words': 4, 'word_freq': {'cat': 4}, 'max_depth': 3, 'num_uniq_words': 1, 'total_length': 12}
    Tree info: {'num_words': 3, 'word_freq': {'catc': 1, 'tcat': 1, 'atca': 1}, 'max_depth': 4, 'num_uniq_words': 3, 'total_length': 12}
    Tree info: {'num_words': 2, 'word_freq': {'catcat': 2}, 'max_depth': 6, 'num_uniq_words': 1, 'total_length': 12}
Input: aaaaaa
    Length of shortest whole repetitive substring: 1
    Tree info: {'num_words': 6, 'word_freq': {'a': 6}, 'max_depth': 1, 'num_uniq_words': 1, 'total_length': 6}
    Tree info: {'num_words': 3, 'word_freq': {'aa': 3}, 'max_depth': 2, 'num_uniq_words': 1, 'total_length': 6}
    Tree info: {'num_words': 2, 'word_freq': {'aaa': 2}, 'max_depth': 3, 'num_uniq_words': 1, 'total_length': 6}
Input: aaaaaba
    Length of shortest whole repetitive substring: 7
    Tree info: {'num_words': 7, 'word_freq': {'a': 6, 'b': 1}, 'max_depth': 1, 'num_uniq_words': 2, 'total_length': 7}