iPhone/Androidアプリのユーザーが検索する必要がある文字列の一覧があります。文字列はアルファベット順にソートされていますが、実際にはそれほど有用ではありません。なぜなら、検索クエリが最初だけでなく文字列のどこにも含まれていれば、結果に文字列を含める必要があるからです。ユーザーが検索クエリを入力しているときに、現在入力した結果を反映するように検索を更新する必要があります。 （たとえば、「cat」と入力すると、入力時に「c」、「ca」、「cat」の結果が表示されます）。私は空から始まり、「検索結果」のスタックを、持っている大きな文字列を効率的に検索する
：
私の現在のアプローチは、次のようです。ユーザーが検索クエリを長くするために何かを入力すると、現在の検索結果をスタックにプッシュし、新しい検索結果のみを検索します（現在の検索結果は現在の検索結果ではなく完全な文字列リストにはありません）この場合の結果）。
ユーザーがbackspaceを押すと、検索結果をスタックからポップして復元する必要があります。これはほぼ即座に行うことができます。
このアプローチは、「後方」検索（検索クエリを短くする）や、検索クエリがすでに十分に長くて結果の数が少なくなる場合に効果的です。しかし、ユーザーが入力する最初の数文字のそれぞれについて、O（n）時間の文字列の完全なリストを検索する必要があります。これはかなり遅いです。
私が考えてきたアプローチの1つは、2文字または3文字のすべての可能な検索クエリの結果の事前コンパイル済みリストを持つことです。このアプローチの問題は、26^2または26^3のリストが必要であり、かなり大量の領域を占めることです。
これ以外の最適化や代替アプローチについて考えることができますか？
の可能重複[サブによって、文字列のコレクションの高速フィルタリング？]（http://stackoverflow.com/questions/1299168/fast-filtering-of-a-を使用することができますstring-collection-by-substring） –
クエリ予測について質問していますか？すなわち、ユーザが 'c 'と入力した場合、あなたは* cat *をどのように予測するべきですか？あるいは、ユーザータイプとして 'c'、' ca'、 'cat'のすべてを検索しますか？クエリ予測は「代替アプローチ」と見なされますか？それともあなたが達成しようとしているものがあまりにも遠いですか？ – amit