原书出处
Introduction to Algorithms, Fourth Edition
32 第32章 字符串匹配
rt of each substring is always nonempty, and so all left-rank values are always positive.
This example illuminates why the COMPUTE-SUFFIX-ARRAY procedure works. The initial ranks established in lines 2–7 are simply the ord values of the characters in the text, and so when line 8 sorts the substr-rank array, its ordering corresponds to the lexicographic ordering of the length-2 substrings. Each iteration of the while loop of lines 10–19 takes sorted substrings of length l and produces sorted substrings of length 2l. Once l reaches or exceeds n, all substrings have been sorted. Within an iteration of the while loop, the MAKE-RANKS procedure “re-ranks” the substrings that were sorted, either by line 8 before the first iteration or by line 18 in the previous iteration. MAKE-RANKS takes a substr-rank array,
which has been sorted, and fills in an array rank[1:n] so that rank[i] is the rank of the
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter032.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea