Adjacent Swaps on Strings
Transforming strings by exchanging elements at bounded distance is applicable in fields like molecular biology, pattern recognition and music theory. A reversal of length two at position i is denoted by (i i+1). When it is applied to π, where π=π1,π2,π3,..., πi,πi+1,πn, it transforms π to π, where π=π1,π2,π3,...,πi-1,πi+1,πi,πi+1,...,πn. We call this operation an adjacent swap. We study the problem of computing the minimuM number of adjacent swaps needed to transform one string of size n into another compatible string over an alphabet cr of size k, i.e. adjacent swap distance problem. O(nlog2n) time complexity algorithms are known for adjacent swap distance. We give an algorithm with O(nk) time for both signed and unsigned versions of this problem where k is the number of symbols. We also give an algorithm with O(nk) time for transforming signed strings with reversals of length up to 2, i.e. reversals of length 1 or 2.
Bhadrachalam Chitturi Hal Sudborough Walter Voit Xuerong Feng
University of Texas at Dallas, Richardson, TX 75080,USA Valdosta State University, Valdosta, GA 31698, USA
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
299-308
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）