文字列と文字列の配列を指定すると、配列内の文字列の最長のサフィックスを見つけます。
例えば
文字列 =google.com.tr
配列 =tr, nic.tr, gov.nic.tr, org.tr, com.tr
戻り値com.tr
特定のコンパレータでバイナリ検索を使用しようとしましたが、失敗しました。
Cコードは大歓迎です。
編集：
準備段階でできるだけ多くの作業を行うことができるソリューションを探していると言うべきでした（接尾辞の配列しかなく、可能な限りあらゆる方法で並べ替えることができ、その周りに任意のデータ構造を構築できます）など）、指定された文字列よりも、この配列でその接尾辞をできるだけ速く見つけます。また、この配列からトライを構築できることも知っています。おそらくこれにより、可能な限り最高のパフォーマンスが得られるでしょう。したがって、ビンサーチのようなアプローチは大歓迎です。
文字列内の文字を一定時間アドレス指定すると仮定すると、この問題は最大のプレフィックスを見つけることと同形です。
しましょうi = 0。
させてS = null
させてc = prefix[i]
ifおよび ifaから文字列を削除します。ifに置き換えます。Aa[i] != cASaa.Length == i + 1
増分しiます。
手順 3 に進みます。
それはあなたが探しているものですか？
例：
プレフィックス = rt.moc.elgoog
配列 = rt.moc、rt.org、rt.cin.vof、rt.cin、rt
prefix[0]0を渡します:配列'r'からarray[j][0] == 'r'何jも削除されません。 i + 1 -> 0 + 1 -> 1は目標の長さですが、長さが 1 の文字列はないため、 のSままnullです。
パス 1:配列から何prefix[1]も削除されません。ただし、長さ 2 の文字列があるため、 になります。't'array[j][1] == 'r'jSrt
パス 2:残りの文字列prefix[2]は'.'andarray[j][2] == '.'であるため、何も変更されません。
パス 3: prefix[3]is'm'およびarray[j][3] != 'm'for rt.org、rt.cin.vofなどrt.cinの文字列が削除されます。
等
接尾辞配列を使用しないのはなぜですか? 多数のサフィックスがある場合に機能します。
複雑、バージョンもO(n(logn)^2)あります。O(nlogn)
ここで c での実装。サフィックス配列をグーグルで試すこともできます。
素朴な疑似回答:
または、並べ替えをスキップして反復し、が一致したよりも大きいbiggestString場合に を割り当てることもできます。currentStringbiggestString
編集 0:
事前に配列を見て、チェックする必要がある「最小限の」要素を検討することで、これを改善できるかもしれません。
たとえば、.comが 20 人のメンバーに表示されている場合、指定された文字列と照合するだけ.comで、20 人の候補を排除できる可能性があります。
編集1：
考え直して、配列内の要素を比較するには、文字列比較を使用する必要があります。比較のために文字列のリストを最適化する試みから得られる利益は、それが理にかなっている場合、そうする前にそれらを比較する費用によって無効になる可能性があると私は感じています。CSタイプがここで私を修正できれば幸いです...
別のナイーブな疑似回答。
ブール値の "found" を false に設定します。「見つかった」が偽である間、ソース文字列を配列内の文字列と比較して配列を反復処理します。一致する場合は、"found" を true に設定して中断します。一致がない場合は、次のようなものを使用strchr()して、最初のピリオドに続く文字列のセグメントに到達します。配列をもう一度繰り返します。一致するまで、またはソース文字列の最後のセグメントが配列内のすべての文字列と比較され、一致しないまで続行します。
あまり効率的ではありません....