shah_entrance's blog

String Concatenation
By shah_entrance, history, 5 years ago, In English

Given a string. Check if the string is a concatenation of any prefix of this string (any number of times concatenation is possible). If present then print the prefix, otherwise -1.

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Let's prove there are always only two prefixes required if it's possible. Let's say we get the answer with more than two strings: $$$s_1, s_2, ..., s_k$$$. Then we can get a string $$$s_1 + s_2 + ... + s_{k - 1}$$$ using only one prefix.

So all we have to do is to find the suffix, such that it is a prefix either. You can do it using Z-function

UPD: I'm quite stupid I guess

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

We can solve it using simple polynomial hash method.

For each prefix, we can calculate the hash value of it. And then, we can try to copy it a lot of times, calculating the hash value as the same time, until the length exceed n.

Time complexity is $$$\sum_{i = 1} ^ {n} [n / i] = \Theta(n log n).$$$

→ Reply