Suffix Arrayアルゴリズム

今日、とあるページでSuffix Arrayという文字列検索用のアルゴリズムの存在を知った。例えば、'abracadabra'という文字列があったとして、'abracadabra', 'bracadabra', 'racadabra', ...というように１文字ずつずらした配列を作成し、ソートして検索用のテーブルを作成しておくというものである。

しかし、これをPythonで実現しようとすると組み込みの文字列クラスでは恐らくできないということに気がついた。できないというのは、もちろん複数のインスタンスを作成しないでという意味である。CやC++ではchar*のテーブルを作成すれば良いだけだが、Pythonではそもそもポインタを生で扱えないので無理である。Cで拡張するしかない。もしくは、そういうことを組み込みの方法でも実現できる方法があるか、ライブラリがあるか調査課題がまたできた。