Advertisement
Guest User

Untitled

a guest
Jun 25th, 2017
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.99 KB | None | 0 0
  1. class Solver:
  2.     def __init__(self, data, num):
  3.         self.data = data
  4.         self.num = int(num) - 1
  5.         self.data_length = len(data)
  6.  
  7.     def decode_BWT(self):
  8.         counter = {}
  9.         transform = []
  10.         for ch in self.data:
  11.             counter[ch] = 0
  12.             transform.append(0)
  13.         for ch in self.data:
  14.             counter[ch] += 1
  15.  
  16.         sum = 0
  17.         k_list = list(counter.keys())
  18.         k_list.sort()
  19.         for ch in k_list:
  20.             sum = sum + counter[ch]
  21.             counter[ch] = sum - counter[ch]
  22.  
  23.         for i in range(0, self.data_length):
  24.             transform[counter[self.data[i]]] = i
  25.             counter[self.data[i]] += 1
  26.  
  27.         j = transform[self.num]
  28.         ans = ''
  29.         for i in range(0, self.data_length):
  30.             ans += self.data[j]
  31.             j = transform[j]
  32.  
  33.         return ans
  34.  
  35.  
  36. if __name__ == '__main__':
  37.     n = input()
  38.     d = input()
  39.     s = Solver(d, n)
  40.     ans = s.decode_BWT()
  41.     print(ans)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement