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()
Finding string roots
python;algorithm;strings;programming challenge;time limit exceeded
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 thoseThe 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 1This 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') == 4assert sroot('abcdefgh012') == 1assert sroot('aaaaaaaaaa') == 10assert sroot('abcdefgh012abcdefgh012') == 2assert sroot('abcdefgh012abcdefgh012x') == 1Lots 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_symbolto this: if not scanned_string:    scanned_string = current_symbolThis can be simplified:matched_characters = matched_characters + current_symbolto this:matched_characters += current_symbol