「各文字列の出現個数」だけが必要で出現位置は不要な場合は、持たせる情報を変えることでこの計算量を削減できる。Arrayの説明自体は上のサイトや他に溢れてるので、割愛。これを線形時間で構築するのがSA-ISと呼ばれるアルゴリズム。SAで文字列検索を行うには、二分探索を用いる。$T$(を接頭辞とした文字列)が出現するかどうかは二分探索で調べられる。複数出現する場合もSA上で連続しているので、始まりと終わりの境界を探索すればよい。複数ある場合に用いる。様々に変えて検索する用途に向く。各接尾辞が出現するかをチェックする。畳み込みは別に文字列に限定したアルゴリズムでは無いのだが、少し応用の利いた一致箇所の列挙に使える。各文字を対応する何らかの数値に置き換える。$S_iT_1+S_{i+1}T_2+...+S_{i+|T|-1}T_{|T|}$」をそれぞれ表す。結果の値から、両者が一致しているかどうかを特定できるような数値への置き換えをしておけば、一致箇所を列挙できる。できるので、わざわざlogが付いてしまうこの方法を使う意味はあまりない。応用の利いた検索をしたいとき、他ではできないことができる。する)では、2つの数列の「係数の和が一致するもの同士のかけ算」の総和が求まる。戻すと、合わせた位置が一致するもの同士のかけ算の総和が求まっていることになる。数値への置き換えが肝となる。中に、“?”(ワイルドカード、この文字は何の文字であってもよい)が含まれるとする。逆数の関係にある数に置き換える。ワイルドカードは0とする。一致しない箇所では他の異なる値になる(可能性が高い)。一致する箇所が一致しないと誤判定されることはないが、一致しない箇所が一致すると誤判定されることは生じる。素数の割り当てを何回か変えて試すとよい。以下で紹介されているアルゴリズムは少し複雑だが、より正答する確率評価がちゃんとできている方法となる。複数の文字列を木構造で表現するデータ構造。トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。短くて似たような単語が沢山あるとき、特に効率的に保持できる。パトリシア木は、それを複数文字も1ノードになり得るとしたもの。実装はやや複雑になるが、長い単語がある場合でも肥大化を防ぐことができる。文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。圧縮の前処理に用いる(同じ文字が連続していれば圧縮効率がよくなる)自然言語でもデータでも、だいたいお決まりの文字(数字)の並びというのが発生しやすいことを利用している。逆に完全にランダムなデータにはあまり効かない(と思う)。