Abelian periods
Input:
w a word of length n
Output:
all the abelian periods of w


T
r
y

i
t


w

L←list with one heap containing (0,1)
for i←2 to n
NewHeap←∅
for all H ∈ L do
(h,p)←ROOT(H)
d←(i-h) mod p
if d=0 then
t←p
else t←d
if Pw(i-t+1,t) ⊆ Pw(i-t-p+1,p) then
ExtractUntilOK(H)
else if d=0 then
REMOVE(H)
INSERT(NewHeap,(h,p))
h←0
while h<(i+1)/2 and Pw(i,h) ⊂ Pw(h+1,i-h) do
INSERT(NewHeap,h,i-h))
h←h+1
L←L ∪ NewHeap
return L

Reference
G. Fici, T. Lecroq, A. Lefebvre and É. Prieur-Gaston
Computing abelian periods
In: J. Holub and J. Žďárek editors, Prague Stringology Conference 2011 (PSC 2011)
Pages 184-196, 2011

Valid XHTML 1.0 Strict CSS Valide !