原书出处
Introduction to Algorithms, Fourth Edition
32 第32章 字符串匹配
on is O(n). Conclude that the algorithm runs in Θ(n) time. 32-3 Burrows-Wheeler transform
The Burrows-Wheeler transform, or BWT, for a text T is defined as follows. First, append a new character that compares as lexicographically less than every character of T, and denote this character by $ and the resulting string by T′. Letting n be the length of T′, create n rows of characters, where each row is one of the n cyclic rotations of T′. Next, sort the rows lexicographically. The BWT is then the string of n characters in the rightmost column, read top to bottom. For example, let T = rutabaga, so that T′ = rutabaga$. The cyclic rotations are rutabaga$ utabaga$r tabaga$ru abaga$rut baga$ruta aga$rutab ga$rutaba a$rutabag
$rutabaga Sorting the rows and numbering the sorted rows gives 1 $rutabaga 2 a$rutabag 3
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter032.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea