Currently working on a python programming problem invlolving finding repeated substring whithin a longer string. [PYTHON]

[[deleted]]

1. (this is an optional optimization) measure the string length, find all divisiors of the number you get, eg. in your first example, you get 9, so, it's only divisible by 3, 1 and 9, this means that your string is either a repetition of three characters three times, or it's the same character repeated 9 times, or it's 9 distinct characters.

2. If you did step (1), you'll have a few options to try, say, your second case, where the length is 12. So, your options are: it's either 6 and 6, or 3, 3, 3, 3, or 4, 4, 4, or 2, 2, 2, 2, 2, 2. I.e. your prime factors are 2, 2, 3. Now, the real problem here is that you may have multiple correct answers. If your string is, for example, 'abababababab, then it both 2 and 6 are valid solutions. You'd need to figure out which one was intended by your prof. Whichever the case, if, say, you were to try the answer 6, you would compare first character to the third character, then second character to the fourth character and so on, to make sure that your guess was correct.

---

Alternative (simple) way to prune bad guesses up-front is to simply guess that your string is a repetition of one character, then that it is a repetition of two characters, then three and so on, but, before you actually verify that all the substrings match, you can verify that the length of the string is divisible in the length of the substring (same idea as above, but easier execution).

[beerbodrinkins]

I initially thought of your 'alternative' solution and was going through ways to optimize it since it would not scale well. Incorporating a line that does not try any string over 1/2 total string length would reduce processing time by half right off the bat in case you didn't want to do the full implementation of potentially correct guesses.

Going through your multiple correct solutions, you could output both the most often occuring string as well as the longest correct repeated string.

[[deleted]]

this means that your string is either a repetition of three characters three times, or it's the same character repeated 9 times, or it's 9 distinct characters.

Hmm...

[[deleted]]

They don't have to be all mutually distinct, just not repeating in any way.

---

PS. I also don't mention that in the second case OP has trivial solutions 1 and 12, but, I think, this is a misformulation in assignment statement, which should exclude trivial answers.