問題タブ [longest-prefix]

171.58.0.0/12 などのプライベート IP アドレスのブロックがある場合、これは基本的に 171.58.0.0 の 32 ビット バージョンと 32 ビットの 1 のビット単位の AND をとることを意味し、最後の 12 ビットは 0 になります。 、その範囲で許容できるプライベート IP アドレスの最長のプレフィックスを取得するには?

プレフィックスの受け入れ可能なプライベート IP アドレスを取得するには?

ありがとう！

これは、比較的些細な問題に対して最も洗練されたJavaScript、Ruby、またはその他のソリューションを考え出すための課題です。

この問題は、最長の一般的な部分文字列問題のより具体的なケースです。配列内で最も長い共通の開始部分文字列を見つけるだけで済みます。これにより、問題が大幅に簡素化されます。

たとえば、の最長の部分文字列[interspecies, interstelar, interstate]は「inters」です。ただし、で「ific」を見つける必要はありません[specifics, terrific]。

シェルのようなタブ補完に関する回答の一部として、JavaScriptでソリューションをすばやくコーディングすることで、問題を解決しました（テストページはこちら）。これがその解決策ですが、少し調整されています。

このコードは、Rubyの同様のソリューションとともにこのGistで利用できます。要旨をgitリポジトリとして複製して試してみることができます。

私はそれらの解決策にあまり満足していません。よりエレガントで実行の複雑さを軽減することで解決できるかもしれないと感じています。そのため、このチャレンジを投稿しています。

私は答えとして、私が最もエレガントまたは簡潔だと思う解決策を受け入れるつもりです。たとえば、私が思いついたクレイジーなRubyハックは&、Stringで演算子を定義することです。

JavaScriptまたはRubyのソリューションが推奨されますが、何が起こっているのかを説明する限り、他の言語で巧妙なソリューションを披露することができます。標準ライブラリのコードのみを使用してください。

更新：私のお気に入りのソリューション

kennebecによるJavaScriptの並べ替えソリューションを「答え」として選択したのは、それが予想外で天才的であると感じたからです。実際の並べ替えの複雑さを無視すると（言語の実装によって無限に最適化されると想像してみてください）、ソリューションの複雑さは2つの文字列を比較するだけです。

その他の優れたソリューション：

• FMによる「regexgreed」は、把握するのに1、2分かかりますが、その優雅さがあなたを襲います。イェフダカッツも正規表現ソリューションを作成しましたが、より複雑です
• commonprefixPythonの場合— Roberto Bonvalletは、この問題を解決するためにファイルシステムパスを処理するために作成された機能を使用しました
• Haskellのワンライナーは圧縮されているかのように短く、美しい
• 簡単なRubyワンライナー

参加していただきありがとうございます！コメントからわかるように、私は多くのことを学びました（Rubyについてさえ）。

すべての標準タグの前にブラウザ固有のプレフィックスを使用できますか?

例えば

上記の有効な CSS は、Firefox が他のすべてのブラウザとは異なる下部パディングを持つようにするためのものですか?

URL の「最長プレフィックス一致」に使用できる標準の python パッケージに関する情報が必要です。私は2つの標準パッケージhttp://packages.python.org/PyTrie/#pytrie.StringTrie & 'http://pypi.python.org/pypi/trie/0.1.1' を調べましたが、そうではないようですURL の最長プレフィックス マッチ タスクに役立ちます。

たとえば、私のセットにこれらの URL がある場合、1->http://www.google.com/mail 、2->http://www.google.com/document、3->http://www.facebook.comなど。

「http://www.google.com/doc」を検索すると 2 が返され、「http://www.face」を検索すると 3 が返されます。

これを行うのに役立つ標準のpythonパッケージがあるかどうか、またはプレフィックスマッチングのためにTrieを実装する必要があるかどうかを確認したかったのです。

URLの数が増えるにつれて拡張性がないため、正規表現のようなソリューションは探していません。

どうもありがとう。

DAOを介してクエリをN回実行するループがあります。私の場合、値が「123456789」のプロパティを持つオブジェクトがあります。C1最初のターンでは、特定のテーブルに対してクエリを実行して、 「123456789」に等しい 列を持つすべてのレコードを取得します。

C12番目のターンでは、この同じテーブルに対してクエリを実行して、 「12345678」に等しい列を持つすべてのレコードを取得します。プレフィックスが最も長いレコードが見つかるまで、以下同様に続きます。

このクエリを複数回実行するのではなく、別のクエリを1回だけ実行してみませんか。これは、パラメータとして文字列 "123456789"を取り、"123456789"C1の最長のプレフィックスである列を持つレコードを返します。しかし、Hibernateでそれを行う方法（可能であれば）、または別の解決策があるかどうかはわかりません。MySQLを使用しています。

（私はこの投稿を見ましたが、Hibernateでそれを行う方法があるかどうか知りたいと思いました。）

最長の単一のサブシーケンスだけでなく、rubyの文字列の配列からすべての一般的なサブシーケンスを見つけようとしています。

これは、入力が

["aaaF hello"、 "aaaG hello"、 "aaaH hello"]

期待される出力は

["aaa"、"こんにちは"]

私は最長の単一サブシーケンスアルゴリズムをいじっていますが、適切な出力を取得する方法を理解できません。ほとんどのアプローチの問題は、最終的な配列に「a」、「aa」、「h」、「he」、「hel」、「hell」などの他の要素があることです。

最長のプレフィックス一致のためにPostgreSQLで正確で高速なクエリを取得するための最良の方法は何ですか？

それは...ですか：

アップデートで使用する予定です。何か案は？

単一の値だけでなく、テーブル内の列に対して最長一致のプレフィックスを実行する必要があります。単一の値には、のようなものを使用しますSELECT value, prefix as lmp FROM aTable WHERE SUBSTRING(value,1, LENGTH(prefix)) = prefix ORDER BY prefix DESC limit 1。

問題は、多くのレコードに対して実行されている場合、テーブルスキャンを実行し、値を1つずつ取得する必要があり、クライアントとサーバー間で大量のトラフィックが発生することです。

サブクエリを含むがストアドプロシージャを含まない単一のクエリでそれを行う方法はありますか？PostgreSQL8.4を使用しています。

接尾辞配列のLCP配列を計算する方法は? 最も効率的である必要はありません。O(n log n) または O(n) で十分です。可能であれば、比較的簡単にコーディングできるもの。