原书出处
Introduction to Algorithms, Fourth Edition
32 第32章 字符串匹配
he order rank[1], rank[2], rank[3], …, rank[n], with the assignment occurring in line 12.
Upon considering a suffix T[i:], line 8 determines the suffix T[j:] that immediately precedes T[i:] in the lexicographically sorted order. At this point, the longest common prefix of T[j:] and T[i:] has length at least l. This property certainly holds upon the first iteration of the for loop, when l = 0. Assuming that line 12 sets LCP[rank[i]] correctly, line 14 (which decrements l if it is positive) and Lemma 32.8 maintain this property for the next iteration. The longest common prefix of T[j:] and T[i:] might be even longer than the value of l at the start of the iteration, however. Lines 9–11 increment l for each additional character the prefixes have in common so that it achieves the length of the longest common prefix.
The index m is set in line 9 and used in the test in line 10 to make sure that the test T
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter032.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea