bwt.rb

module BWT
    module_function
    def convert(str)
        (0...str.size).to_a.sort!{|l,r| str[l..-1] <=> str[r..-1]}.map!{|e| str[e-1]}*""
    end
    
    def convert_i(str)
        idxlist = (0...str.size).to_a.sort!{|l,r| str[l..-1] <=> str[r..-1]}
        head = idxlist.index(0)
        return [idxlist.map{|e| str[e-1]}*"", head]
    end
    
    def revert(str, head)
        stridx = []
        bucket = {}
        str.chars.each{|c|
            bucket[c] ||= 0
            stridx << bucket[c]
            bucket[c] += 1
        }
        table = {}
        sum=0; bucket.sort.each{|k,v|
            table[k] = sum
            sum += v
        }
        orig = ""
        str.size.times{
            orig << str[head]
            head = table[str[head]] + stridx[head]
        }
        orig.reverse!
    end
    
    def search(bwt,pattern,sum=nil)
       # TODO: 
    end
    
    def cusum(str)
        bucket = {}
        str.chars.each{|c|
            bucket[c] ||= 0
            stridx << bucket[c]
            bucket[c] += 1
        }
        table = {}
        sum = 0
        bucket.sort.each{|k,v|
            table[k] = sum
            sum += v
        }
        table
    end
end


text = gets.chomp
p text
bwt = BWT::convert(text)
p bwt
p BWT::revert(bwt, bwt.index('$'))