Problem Statement:
given string S of length N (N<=2e5) , find smallest string by length which is a pattern of S (this string can be equal to string S by append it in some positive integer times)
For example:
Input: abcdabcdabcdabcd ==> Answer: abcd
Input: aabbaabbaabbaabb ==> Answer: aabb
Input: aaaaaaaaaaaaaaaa ==> Answer: a
Input: codeforces ==> Answer: codeforces
how to solve this in nlogn time? thank you very much in advance.
I think it can be done with binary search on the length of the pattern
You can easily write can function in O(n)
It can't because this function is not monotonic.
Ohh I have not noticed that sorry...
Do KMP O(N), then possible answer is n-pi[n-1]. Check again in O(N) if that len is ok.
You do not require the second O(N) check. Just check if n-pi[n-1] completely divides n or not.
You mean first I should make the partial or pi array for a given string like string = "abcdabcdabcdabcd" partial/pi = [0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
then 16 — 12 = 4 and 4 divides 16 completely hence return the first 4 characters of string? Please correct if I am wrong :)
Yes this is what I meant
Yes, another way to think of KMP pi values is — what is the length of the longest proper prefix that is also a suffix, so if pi[15] == 12, this means that the first 12 characters are equal to the last 12 characters, which you can deduce means "middle" shared string with length 8 must also be 4 periodic as ankurdua15 corrected me, and etc.
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.
You can define number_of_factors as $$$N ^ {1 / 3}$$$ it's strictly okay.
thanks TripleM5da...
Could you plz do my favor, I need some help in this, it is the standard problem fence algorithm, but if I do that with dp solution for n = 4, k = 3, it gives 66, but if try with the brute force it gives 60.
you can use $$$dp_{n,c}$$$ where $$$n$$$ is the number of fences left to color and $$$c$$$ is the number of adjacent equal fences for now at any point you can either choose $$$(k - 1)$$$ colors to pain this fence without adding to c or choose the color of the fence before me and add $$$1$$$ to $$$c$$$.
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: