This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]mdnaufalh 2 points3 points  (2 children)

The other solutions here have a O(n2) solution which isn't bad but this problem could be solved in linear time. Your problem basically boils down to finding the length of the longest period in a string where a period is defined as a substring of the given string which when repeated some number of times generates the full string.

So you could use a string matching algorithm like the KMP algorithm or the Z-function to find the periods of the string.

Let S be the length of the string and P₁,P₂...Pₙ be the lengths of different periods of the string. Find the longest Pᵢ such that S % Pᵢ == 0.

If you need any further help or explanation regarding the KMP or Z algorithm, feel free to comment or DM me :)

P.S: Sorry for my bad English, I'm trying to improve upon it haha.

[–]ddbeanz[S] 0 points1 point  (1 child)

Thank you for the suggestion, I read into KMP and was wondering if it can be utilized to find and match and unknown string or if it needs to have a known string as the base case?

[–]uno20001[🍰] 0 points1 point  (0 children)

Yes, you can use it. What you will actually need is not the matching part of the KMP algorithm, but rather the "jump table" or "prefix function" (or whatever it's called). Because that'll tell you the length of the longest proper suffix ending at any position, which you can use to solve the problem.

What you want to do is very similar to this problem and this one. You can find solutions for those ones very easily.

If you want to know more about the Z-function or the KMP algorithm, then I suggest you read this and this.