I think it can be done with binary search on the length of the pattern

l=0
r=len(s)
ans=len(s)
while l<=r:
    mid=l+(r-l)//2
    if can(mid):
       r=mid-1
       ans=mid
    else:
        l=mid+1
return ans

You can easily write can function in O(n)

Do KMP O(N), then possible answer is n-pi[n-1]. Check again in O(N) if that len is ok.

This problem can be solved by using the Z algorithm or KMP. The first observation we can see is that if a substring can be repeated some number of times to form the string, it has to be a prefix of the original string.

So, after computing the Z function of the string, we can see that a prefix of length i can be repeated to form the string if Z[i] + i equals the string length.

Time complexity is O(n)

I think one of the ways, let n = length(string), store the factors of n in an array, then check only for that length, because we know that, the length of the substring must divide the n.

So, to precompute the factors, it will be O(sqrt(n)), then for checking for each length = O(n), overall time complexity O(number_of_factors(n) * n)). Ping me, if you get correct.

First get $$$Z_i$$$ using Z-function where $$$Z_i$$$ is the largest prefix matched at the $$$i-th$$$ suffix then you can just iterate over the size of the pattern and check if $$$Z_{sz}, Z_{sz*2}, \dots ,Z+{(n / sz) * sz}$$$ $$$\ge sz$$$.

A solution with rolling hashing.

For each prefix with length divisor length of string, iterate through the corresponding substrings, and check with hash whether they match.

time complexity: