Jun. Jui. 2017 Aug.
02 030405060708
09 101112131415
1617 1819202122
23 242526 27 2829
Click Seminar

Past Seminars

DateJuly 24, 2017 (Monday)
SpeakerShiho Sugimoto 
TitleComputing Abelian string regularities based on RLE 
Two strings x and y are said to be Abelian equivalent if x is a permutation of y, or vice versa. If a string z satisfies z = xy with x and y being Abelian equivalent, then z is said to be an Abelian square. If a string w can be factorized into a sequence v1,...,vs of strings such that v1 , . . . , vs−1 are all Abelian equivalent and vs is a substring of a permutation of v1, then w is said to have a regular Abelian period (p,t) where p = |v1| and t = |vs|. If a substring w1[i..i+l−1] of a string w1 and a substring w2[j..j + l − 1] of another string w2 are Abelian equivalent, then the substrings are said to be a common Abelian factor of w1 and w2 and if the length l is the maximum of such then the substrings are said to be a longest common Abelian factor of w1 and w2. We propose efficient algorithms which compute these Abelian regularities using the run length encoding (RLE) of strings. For a given string w of length n whose RLE is of size m, we propose algorithms which compute all Abelian squares occurring in w in O(mn) time, and all regular Abelian periods of w in O(mn) time. For two given strings w1 and w2 of total length n and of total RLE size m, we propose an algorithm which computes all longest common Abelian factors in O(m2n) time.