原书出处
Introduction to Algorithms, Fourth Edition
32 第32章 字符串匹配
ank value is 1 greater than the rank value for the previous instance of a, in position 1.
There is enough information in BWT and rank to reconstruct T′ from back to front. Suppose that you know the rank r of a character c in T′. Then c is the first character in row r of the sorted cyclic rotations. The last character in row r must be the character that precedes c in T′. But you know which character is the last character in row r, because it is BWT[r]. To reconstruct T′ from back to front, start with $, which you can find in BWT. Then work backward using BWT and rank to reconstruct T′. Let’s see how this strategy works for rutabaga. The last character of T′, $, appears in position 7 of BWT. Since rank[7] = 1, row 1 of the sorted cyclic rotations of T′ begins with $. The character that precedes $ in T
′ is the last character in row 1, which is BWT[1]: a. Now we know that the last two charac
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter032.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea