Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

ProblemAsker's blog

How to find smallest substring that is a pattern of it's string in nlogn?
By ProblemAsker, 4 years ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it -49 Vote: I do not like it

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)

→ Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    You do not require the second O(N) check. Just check if n-pi[n-1] completely divides n or not.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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 :)

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes this is what I meant

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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)

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You can define number_of_factors as $$$N ^ {1 / 3}$$$ it's strictly okay.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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$$$.

        → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

$$$O(\sum_{d:d|n}\frac{n}{d}) = O(n\cdot \log\log n)$$$
→ Reply