找周期子字的算法

§1.引言 考虑有限字母表A上字X=x_1x_2…x_n,|X|=n,x_i∈A,i=1,2,…,n;X的子字S=x_ix_(i 1)…x_j,j>i,称为周期子字,若存在p>0,使j-i 1≥2p并且有x_l=x_(l p),l=i,i 1,…,(j-p).p称为S的周期,有时把S称为终于i的周期子字.令P=x_i…x_(i p-1),p=|P|,则S可写成P~‖prefix(P),k≥2,prefix(P)表示P的某个字首。‖表示并置运算。P表示k个P并置。