algorithm - Find the smallest period of input string in O(n)? -

given following problem :

definition :

let s string on alphabet Σ .s' smallest period of s if s' smallest string such :

s = (s')^k (s'') ,

where s'' prefix of s. if no such s' exists , s not periodic .

example : s = abcabcabcabca. abcabc period since s = abcabc abcabc a, smallest period abc since s = abc abc abc abc a.

give algorithm find smallest period of input string s or declare s not periodic.

hint : can in o(n) ...

my solution : use kmp , runs in o(n) .

by definition of problem , s = (s')^k (s'') , think if create automata shortest period , , find way find shortest period , i'm done.

the problem put fail arrow of automata ...

any ideas appreciated ,

regards

i'm not sure understand attempted solution. kmp useful subroutine, though -- smallest period how far kmp moves needle string (i.e., s) after complete match.