CODEWITHSUNDEEP
stringalgorithm
Omar
Omar

Reputation: 13

Detect periodical string

I am trying to solve this problem, I couldn't get to linear time.

A string T is called periodical if it can be represented in the form of T=PPP..P.
Design a linear time algorthim for deciding whether a given T is periodical,and if it's true, find the shortest period.

My approach: if T=AB=BA then T is periodical, my algorithm keep checking if string can be represented like that,if yes then I check for half of it.
It takes O(n*log(n)) time.

Thanks guys

Upvotes: 0

Views: 194

Answers (1)

Sorin
Sorin

Reputation: 11968

KMP search algorithm computes, in part, the longest substring that's both a prefix and a suffix (shorter than the entire string).

If you apply it to a periodical string you'll get 

len(string) - len(substring) = period

len(substring) must be > len(string) / 2, otherwise there's no period.

The period found will also be the shortest period.

KMP is linear.

So check it out (wikipedia).

Upvotes: 0

Related Questions