1

文字列のセットを一意にすることができる最小文字数 (最初の文字から始まる) は何ですか。

たとえば、文字列のセット:

{
    'january',
    'february',
    'march',
    'april',
    'may',
    'june',
    'july'
}

ここで、'j' は 'june' と 'july' の両方にあるため、1 番目の文字だけを使用することはできません (また、'm' は 'march' と 'may' にあります)。また、「ま」は「march」と「may」の両方にあるため、最初の 2 文字は使用できません。

でも、使えるのは最初の3文字！

この数値を返すための最適なアルゴリズムは何ですか (明らかなブルート フォース以外に) ?

4

2 に答える 2

2

最適化できる最初のことは、必要なプレフィックスのサイズに対してバイナリ検索を行うことです。関数は単調です。指定された文字数 n で十分な場合は、n より大きい値でも構いません。

2 番目 - 各文字列の特定のプレフィックスのハッシュ コードを一定時間で取得できるように、各文字列のローリング ハッシュを計算できます。したがって、もちろんより高速な文字列ではなく、数値（ハッシュコード）の一意性を確認する必要があります。Rabin-karp のようなローリング ハッシュをお勧めします。

于 2013-04-25T07:12:54.193 に答える