TY - GEN
T1 - Inferring strings from full abelian periods
AU - Nishida, Makoto
AU - I, Tomohiro
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2015
Y1 - 2015
N2 - Strings u, v are said to be Abelian equivalent if u is a permutation of the characters appearing in v. A string w is said to have a full Abelian period p if w = w1 …wk, where all wi’s are of length p each and are all Abelian equivalent. This paper studies reverse-engineering problems on full Abelian periods. Given a positive integer n and a set D of divisors of n, we show how to compute in O(n) time the lexicographically smallest string of length n which has all elements of D as its full Abelian periods and has the minimum number of full Abelian periods not in D. Moreover, we give an algorithm to enumerate all such strings in amortized constant time per output after O(n)-time preprocessing. Also, we show how to enumerate the strings which have all elements of D as its full Abelian periods in amortized constant time per output after O(n)-time preprocessing.
AB - Strings u, v are said to be Abelian equivalent if u is a permutation of the characters appearing in v. A string w is said to have a full Abelian period p if w = w1 …wk, where all wi’s are of length p each and are all Abelian equivalent. This paper studies reverse-engineering problems on full Abelian periods. Given a positive integer n and a set D of divisors of n, we show how to compute in O(n) time the lexicographically smallest string of length n which has all elements of D as its full Abelian periods and has the minimum number of full Abelian periods not in D. Moreover, we give an algorithm to enumerate all such strings in amortized constant time per output after O(n)-time preprocessing. Also, we show how to enumerate the strings which have all elements of D as its full Abelian periods in amortized constant time per output after O(n)-time preprocessing.
UR - http://www.scopus.com/inward/record.url?scp=84951950947&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84951950947&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-48971-0_64
DO - 10.1007/978-3-662-48971-0_64
M3 - Conference contribution
AN - SCOPUS:84951950947
SN - 9783662489703
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 768
EP - 779
BT - Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings
A2 - Elbassioni, Khaled
A2 - Makino, Kazuhisa
PB - Springer Verlag
T2 - 26th International Symposium on Algorithms and Computation, ISAAC 2015
Y2 - 9 December 2015 through 11 December 2015
ER -