← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

32 第32章 字符串匹配

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.769Z

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