Finding string roots

Question

This is the following Python code that I have coded for an algorithmic problem online. For each line of input, the goal is to find the greatest number of repeating blocks into which the string can be split. For example, if the input is abcabcabcabc, then the output should be 4, because the string is equal to 4 repetitions of abc.

The online compiler says "Time Limit Exceeded". Where in the following code can I optimize to make it much more efficient in terms of time?

inputString = raw_input()
while (inputString !='*'):
   scanned_string = ""
   matched_characters = ""
   frequency = 0
   if (len(inputString) == 1):
     print frequency
   for current_symbol in inputString:
     if not scanned_string:
        scanned_string = scanned_string + current_symbol
     if scanned_string:
        matched_characters = matched_characters + current_symbol
        if (scanned_string.startswith(matched_characters)):
            if (len(scanned_string) == len(matched_characters)):
                frequency = frequency + 1
                matched_characters = ""
        else:
            scanned_string = scanned_string+matched_characters
            matched_characters = ""
            frequency = 1
   print frequency
   inputString = raw_input()

Answer 1

Notice that:

• The length of a root must be a divisor of the length of the input string: you could skip other lengths. For example for the input string "abcabcabc" (length = 9), "ab" (length = 2) or "abcd" (length = 4) cannot be a root, so no need to check those
• The length of a root must be less than equal to half the length of the input string, otherwise it's the input string itself (frequency = 1)

Taking the above into consideration, this implementation should be faster:

def sroot(text):
    text_len = len(text)
    for segment_len in range(1, text_len // 2 + 1):
        if text_len % segment_len != 0:
            continue
        frequency = text_len // segment_len
        if text[:segment_len] * frequency == text:
            return frequency
    return 1

This can be further improved too. For example, instead of iterating until text_len // 2, it would be enough to iterate until math.sqrt(text_len), and when finding a divisor, also try its factor pair as a possible segment. For example for text_len = 100, when finding segment_len = 5, also try segment_len = 100 / 5 = 20. Iterating until 10 will be a lot faster than iterating until 50 as in the example implementation above.

There are several coding style issues in your code:

• It's good to put the main logic inside a function. It makes it easier to test. For example you can add assertions like this to test your solution:

  assert sroot('abcabcabcabc') == 4
  assert sroot('abcdefgh012') == 1
  assert sroot('aaaaaaaaaa') == 10
  assert sroot('abcdefgh012abcdefgh012') == 2
  assert sroot('abcdefgh012abcdefgh012x') == 1
  

• Lots of unnecessary parentheses, for example in:

  while (inputString !='*'):
  if (len(inputString) == 1):
  

• This can be simplified:

   if not scanned_string:
      scanned_string = scanned_string + current_symbol
  

  to this:

   if not scanned_string:
      scanned_string = current_symbol
  

• This can be simplified:

  matched_characters = matched_characters + current_symbol
  

  to this:

  matched_characters += current_symbol
  

Answer 2

Mysterious special case

For any inputString with length 1, you print two lines of output: 0 followed by 1. The incorrect 0 comes from the special case

if (len(inputString) == 1):
  print frequency

which as far as I can tell should not be there at all.

Style

Consistent indentation is important, especially in Python, where whitespace matters. Use 4 spaces, as recommended in PEP 8.

inputString should be input_string to be consistent with the naming style and Python guidelines.

It is customary to omit parentheses after while, if, and for.

You should split your code according to responsibilities. I recommend the following outline:

def string_root(s):
    …
    return n

def lines(terminator='*'):
    s = raw_input()
    while s != terminator:
        yield s
        s = raw_input()

if __name__ == '__main__':
    for line in lines():
        print string_root(line)

Advantages include:

• The main loop read like English. It makes it obvious that each line is treated as an independent problem, unaffected by all other lines.
• The two calls to raw_input() are close to each other. (Unfortunately, there's no do-while loop in Python.)
• The string_root() function is independently testable.

Algorithm

You've implemented a brute-force solution. The complexity is \$O(L^2)\$, there \$L\$ is the length of inputString. (You can tell because for current_symbol in inputString is \$O(L)\$, and scanned_string.startswith(matched_characters) is also \$O(L)\$, and there are no break statements anywhere to serve as shortcuts.)

To bring it down to \$O(L)\$, you would need a smarter string-matching algorithm. The Z Algorithm is useful here: it detects string self-similarities in \$O(L)\$ time.

>>> compute_z('abc' * 4)
[12, 0, 0, 9, 0, 0, 6, 0, 0, 3, 0, 0]

The result above means that 'abcabcabcabc' has

• 12 leading characters in common with itself
• no leading characters in common with itself after dropping the initial 'a'
• no leading characters in common with itself after dropping the initial 'ab'
• 9 leading characters in common with itself after dropping the initial 'abc'
• …

This implementation works in \$O(L)\$ time.

def string_root(s):
    z = compute_z(s)
    z_iter = enumerate(z)
    _, s_len = next(z_iter)
    for block_len, remain_len in z_iter:
        if remain_len == s_len - block_len and remain_len % block_len == 0:
            return s_len // block_len
    return 1

Documentation and testing

A doctest would be useful here.

def string_root(s):
    """Returns the maximum number of repeating blocks into which string s
    can be split.

    >>> string_root('abcabcabcabc')
    4
    >>> string_root('abcdefgh012')
    1       
    >>> string_root('aaaaaaaaaa')
    10
    >>> string_root('abcabcabcabcd')
    1
    >>> string_root('abcabcdabcabcd')
    2
    >>> string_root('abcabcabcabx')
    1
    """
    z = compute_z(s)
    …

Then you can test the code using

import findsr
import doctest
doctest.testmod(findsr)