5
\$\begingroup\$

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))
\$\endgroup\$
  • 1
    \$\begingroup\$ Your examples don't show whether the covering substring may overlap (copies of itself, obviously): what about 'sassass'? \$\endgroup\$ – greybeard Oct 20 '16 at 21:55
  • 1
    \$\begingroup\$ See also: Check if string is repetition of an unknown substring (& linked/related). \$\endgroup\$ – greybeard Oct 24 '16 at 6:22
  • 1
    \$\begingroup\$ This has two parts/questions (frowned upon on SE): Review this code for finding the period of a string and How to find the period of a string fast: the latter would be a better fit for SO or CS, depending on presentation&focus. (If you don't post such a question, I more likely than not will do so (,now that I think I know how to make the approach presented by RobAu work).) \$\endgroup\$ – greybeard Oct 24 '16 at 21:21
  • 1
    \$\begingroup\$ (Ruby, what does this line mean n.times do |i| (RTFM?) the identifier list between bars receives value tuples from the iterator before the do.) \$\endgroup\$ – greybeard Oct 25 '16 at 3:02
  • 1
    \$\begingroup\$ how [the referred post] is related to RobAu's work? It is totally different. Right. If I read your points wrong At least one of us is confused as to what this post is about, which is the one I commented. \$\endgroup\$ – greybeard Oct 25 '16 at 3:08
2
+50
\$\begingroup\$

You don't need a trie? Just keep the 'shortest repeating current substring' (Which would end up being O(n) )

The idea is simple: for each chararcter try to match it to the current shorterst 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 it's begin and continue.

For example:

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), next

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
\$\endgroup\$
  • 1
    \$\begingroup\$ I do not quite get what [does RobAu] mean "(a matches start of aaab)" -- yes a [matches] start of aaab, but how it is related to wholly repetitive string match? I read is as inspected head can be covered by repetitions and matches as the string might still be covered by the current candidate (and nothing not beginning with this candidate will do). \$\endgroup\$ – greybeard Oct 19 '16 at 8:16
  • 1
    \$\begingroup\$ Sorry for my bad explanantion :) I mean that each time you have a shortest repeating subtring, you try to match it from the current character. So aaab is candidate if the input from the current location has a, a, a. If the next one would be a again, there is no longer a match and I re-initialize the shortest repeating subtring to be the entire visited string. Else, if the input from the current location was a, a, a, b, we matched the entires shortest repeating substring, and we start again by matching a, a, a, b etc. \$\endgroup\$ – RobAu Oct 19 '16 at 9:47
  • 1
    \$\begingroup\$ Working without a trie or some such might run into trouble with strings like "aabaaabaa". Candidates a, a, aab, aab, aab, aaba, aaba, aaba are fine, but going to aabaa seems to need a re-parse. \$\endgroup\$ – greybeard Oct 20 '16 at 21:40
  • 1
    \$\begingroup\$ Your example would yield, aabaaabaa as shortest whole repetitive substring \$\endgroup\$ – RobAu Oct 21 '16 at 5:09
  • 2
    \$\begingroup\$ @LinMa Whenever there is a mismatch, it means the current string does not have a shorter repeating substring, because else that would be a match. \$\endgroup\$ – RobAu Oct 21 '16 at 8:18
4
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ This won't work for overlapping matches. If the OP needs that, he could also change the regex to (.+?)(?=\1). \$\endgroup\$ – яүυк Oct 12 '16 at 9:56
  • 1
    \$\begingroup\$ @Dex'ter: Can you explain what you mean by an "overlapping match" and give an example? Do you mean something like ababa → 3? \$\endgroup\$ – Gareth Rees Oct 12 '16 at 10:01
  • 1
    \$\begingroup\$ Well, maybe, because xkcd.com/1171 ;) \$\endgroup\$ – mkrieger1 Oct 12 '16 at 11:08
  • \$\begingroup\$ Hi Gareth, agree regular expression is better and more efficient for work. I just practice coding (even if some routines are already embodied in python sdk) and learn from expert like you here. If you could comment on my original question, it will be great. \$\endgroup\$ – Lin Ma Oct 16 '16 at 0:32
  • 1
    \$\begingroup\$ Tempted as I am to down-vote this to favour ideas to improve time complexity, the question explicitly asked for any code review comments for my current code, too. \$\endgroup\$ – greybeard Oct 22 '16 at 2:52
4
\$\begingroup\$

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()
\$\endgroup\$
  • 1
    \$\begingroup\$ "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. " -- I like this comments. \$\endgroup\$ – Lin Ma Oct 17 '16 at 5:12
1
\$\begingroup\$

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}
\$\endgroup\$
  • \$\begingroup\$ Agree with arvindpdmn, it is a better way since history is not easy to track here. \$\endgroup\$ – Lin Ma Oct 17 '16 at 0:33
  • \$\begingroup\$ arvindpdmn, appreciate for your reply and vote up for your both posts. I have a high level general question, do you think building trie tree improve the algorithm performance? Or I should choose some other algorithm? \$\endgroup\$ – Lin Ma Oct 17 '16 at 0:34
  • 1
    \$\begingroup\$ Lin Ma, thanks for pointing out the problem with input abcabcabb. Will correct the code in a minute. \$\endgroup\$ – coder.in.me Oct 17 '16 at 9:39
  • 1
    \$\begingroup\$ Don't have much experience with trie. Here's a comparison that someone did: code.google.com/archive/p/java-algorithms-implementation. I discovered that trie is used in predictive searching. Suppose I want to search for "water" and typed "wa" then trie can use these first characters to show the entire subgraph below it. It would be fast because the trie graph has already been created in advance based on a fixed dictionary of words. If I type "w", 25 other possibilities are immediately eliminated, which would not be possible with a binary search tree. \$\endgroup\$ – coder.in.me Oct 19 '16 at 8:07
  • 2
    \$\begingroup\$ Since this is a code review, I reviewed and improved your code based on TrieNode. But if this problem is given to me, I might have used regex or substrings as suggested by others. Just maintain a list of substrings rather than create TrieNode objects. In terms of performance, we would have to look at the actual implementation. Some people contrast trie and hash tables but I think they are equivalent. A first level hash key is based on the first character; second level hash key on the second character -- so it's really implementing trie as a multilevel hash table. \$\endgroup\$ – coder.in.me Oct 19 '16 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.