Method for finding repeating the sequence of characters LAND finite alphabet and method of calculating the auxiliary array

摘要

FIELD: information technology.;SUBSTANCE: to find maximum sections in a finite sequence of characters x[i] (0≤i≤N) of a finite alphabet, which are repetitions of previously encountered sections, two bit arrays beg[i] and end[i] are created in computer memory. All elements of said bit arrays are populated with zeros. The sequence s1[i] is calculated for all N values of indices i, where s1[i] is the maximum length of the linear section of said data sequence. All said maximum sections are defined as all intervals x[m,n] for which the initial index m satisfies the condition s1[m]sl[m-1]-1, and the final index n is equal to m+sl[m]-1, for which, for each value i, the fulfillment of the condition s1[i]sl[i-1]-1 is checked, and if the condition is met, values beg[i]=1 and end[i+s1[i]]=1 are set in the bit arrays beg[i] and end[i]. The set of all said maximum sections is recovered on the two bit arrays beg[i] and end[i].;EFFECT: reduced amount of memory required to display all maximum repeating sections.;3 cl, 2 dwg