# 練習 22：后綴數組 > 原文：[Exercise 22: Suffix Arrays](https://learncodethehardway.org/more-python-book/ex22.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 我想告訴你一個關于后綴數組的故事。在一段時間里，我正在西雅圖的一家公司面試，當時好奇的是如何最有效地創建一個用于可執行二進制文件的`diff`。我的研究給我帶來了后綴數組和后綴樹。后綴數組只是，將字符串的所有后綴排序，儲存到有序列表中。后綴樹是類似的，但是比列表更像`BSTree`。這些算法相當簡單，一旦你進行了排序操作，它們就具有很快的性能。他們解決的問題是，找到兩個字符串之間最長的公共子串（或者在這種情況下是字節列表）。 你可以在 Python 中輕易創建一個后綴數組： ```py >>> magic = "abracadabra" >>> magic_sa = [] >>> for i in range(0, len(magic)): ... magic_sa.append(magic[i:]) ... >>> magic_sa ['abracadabra', 'bracadabra', 'racadabra', 'acadabra', 'cadabra', 'adabra', 'dabra', 'abra', 'bra', 'ra', 'a'] >>> magic_sa = sorted(magic_sa) >>> magic_sa ['a', 'abra', 'abracadabra', 'acadabra', 'adabra', 'bra', 'bracadabra', 'cadabra', 'dabra', 'ra', 'racadabra'] >>> ``` 正如你所看到的，我只是按順序取下字符串的后綴，然后對列表進行排序。但是，這對我有什么用呢？一旦我有了這個列表，那么我可以通過這個列表的二分搜索，來找到我想要的任何后綴。這個例子很簡陋，但是在實際的代碼中，你可以很快地做到它，你可以跟蹤所有的原始索引，所以你可以引用后綴的原始位置。它與其他搜索算法相比非常快，對于 DNA 分析等事情非常有用。 回到西雅圖的面試。我在這個寒冷的房間被 C++ 程序員面試，為了一份 Java 工作。你可以斷定，這不是一個非常有趣的面試，我絕對不會認為我會得到這份工作。在多年的時間中，我沒有寫過任何 C++，而且這個工作是針對 Java 的，當時我是一個 Java 專家。下一個面試官來了，他問我：“如何在字符串中尋找子串？” 太棒了！我在空閑時間里一直在研究這個問題。我當然知道！我跳起來走到白板，向那個家伙解釋如何制作一個后綴樹，它如何提高搜索性能，修改后的堆排序如何更快，后綴樹的工作原理，為什么它比三叉搜索樹更好，以及如何在 C 中實現。我想，如果我可以展示如何在 C 中寫出來，那么這將證明，我不只是一個核心能力的 Java 碼工。 那個家伙很震驚，就像我在采訪室里打開一袋新鮮的榴蓮一樣。他看著董事會，并且有些結巴，“呃，我是在尋找一些有關 Boyer-Moore 搜索算法的東西嗎？你知道嗎？我愁眉苦臉地說：“是啊，就像 10 年前一樣。” 他搖搖頭，拿著他的東西，起身說：“好吧，我會讓大家知道我的想法。” 幾分鐘后，下一個面試官來了。他抬頭看著白板，笑了起來并嘲笑我，然后問我另一個 C++ 模板元編程問題，我無法回答。我沒有得到這份工作。 ## 挑戰練習 在這個練習中，你將會使用我的 Python 小會話并創建自己的后綴數組搜索類。該類將使用一個字符串，將其拆成后綴列表，然后對其進行以下操作： > `find_shortest` > 找到以它開始的最短子串。在上面的例子中，如果我搜索`abra`，那么它應該返回`abra`，而不是`abracadabra`。 > `find_longest` > 找到以它開始的最長子串。如果我搜索`abra`，你返回`abracadabra`。 > `find_all` > 查找以它開始的所有子串。這意味著`abra`返回`abra`和`abracadabra`。 你將需要對此進行良好的自動測試，并進行一些性能測量。我們將在以后的練習中使用它們。完成之后，你需要進行研究性學習來完成這個練習。 ## 研究性學習 + 一旦你的測試正常工作，使用你的`BSTree`重寫它，進行后綴排序和搜索。你還可以使用每個`BSTreeNode`的`value`，來跟蹤原始字符串中存在該子串的位置。然后，你可以保留原始字符串。 + `BStree`如何為不同搜索操作更改你的代碼？是否使其更簡單或更難？ ## 深入學習 徹底研究后綴數組及其應用。它們非常有用，但不是被大多數程序員熟知。