An optimal algorithm to compute all the covers of a string (Q1329417)

A string \(u\) is a cover of a string \(x\) if every letter in \(x\) is inside a copy of \(u\). For example \(aba\) is a cover of \(ababaabaabaaba\). This paper characterizes all covers of \(x\) in terms of an easily computed normal form for \(x\). This leads to an algorithm that computes all covers of \(x\) in time \(\Theta (| x |)\).