Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### ftiasch's blog

By ftiasch, 7 years ago, , http://main.edu.pl/en/archive/pa/2011/naj

problem: find length of shortest period after removing exactly one character from the given string.

the period of string s is the shortest string t which s is a prefix of t k for sufficiently large k, where t k denotes t + t + ... + t ( k times).

i have already got some idea of the algorithm, is there any algorithm running in O(N) time?  Comments (15)
 » You have to use segment tree and BS Tree their subtrees' roots being hashed (using perfect hashing !) and finally BS on answers while also balancing the red-black tree, and maintaining the fact that the sum is even if the number of subtrees' nodes are 2^p-1, where p is any prime number.Also take into account that 64MB stack is not enough to recursively solve the problem. You gotta use an iterative method.
•  » » i saw you use segment tree in your solution, is your the running time be O(N log N)?
•  » » » Sometimes. It dependson weather.
•  » » Guys, this man(i mean Dixtosa ) always write the same text to all blogs that ask for help.he wrote the same thing in this blogand do you know why he do so? he do so to get negative votes and make his Contribution the least one in codeforces so give him positive vote :) .
•  » » » 7 years ago, # ^ | ← Rev. 4 →   ur awesome :dit must have taken you long to infer that, doesn't it? :DLastly, don't fucking ever try to decipher me again plz :D
•  » » » » no it didn't take me long to infer that :)By the way, I gave you positive votes to all your comments :)
 » Can you explain your O(NLogN) idea? May be we can improve it to O(n) together.
•  » » 7 years ago, # ^ | ← Rev. 4 →   the running time is due to .Do enumeration on the period length L. Assume that we DO NOT remove any of the first L characters, we can check the answer in O(N / L) time.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   The length of the period is always a divisor of N - 1 so the actual running time is O(σ (N - 1)) = O(N) I don't know how to read problem statements
•  » » » » In this task the length of the period can be not a divisor of N — 1.
•  » » » How is the time complexity of O(N / L) achieved?
•  » » » » my approach need some data structure to test the equality of two substrings. (hash, suffix array etc). since the period is known by enumeration, we can extend the period from both directions, so that the only character left is the one should be removed.
•  » » » » » N + N/2 + N/4 + N/8 + N/16 ... N/(2^k)=N(1+1/2+1/4+1/8 ... 1/(2^k))but:1/2 + 1/4 + 1/8 + 1/16 ... 1/(2^k) is always less than 1 (whatever the value of k)so:N(1+1/2+1/4+1/8 ... 1/(2^k))=N(1+1)=2*Nyour solution is already O(N)
•  » » » » » » you have made some mistake i think. the summation should be n + n / 2 + n / 3 + ... + n / n instead of n + n / 2 + n / 4 + n / 8 + ... thus the running time will still be O(n log n)thank you at all.
•  » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   sorry but that was not clear in the first line in your comment