1

N個の単語のセットと整数Kが与えられます。最初のk文字と最後のk文字がまったく同じである場合、2つの単語は同じグループに含まれます。同一のk文字を超える、または同一のk文字未満の場合、その単語は同じグループに含まれていません。例：k=3の場合。

「abcdefg」と「abczefg」は同じグループにあります
「abcddefg」と「abcdzefg」は同じグループにありません（最初のk + 1文字は同じです）
「abc」と「abc」は同じグループにあります

単語は複数のグループに含めることができます。例（k = 3）：
「abczefg」と「abcefg」はグループを形成します
「abczaefg」と「abcefg」はグループを形成します
「abczaefg」と「abczefg」は同じグループにありません（最初のk + 1文字は同一です） ）。

問題は、最大数の単語を含むグループの数を見つけるように私に求めます。

Trie（またはプレフィックスツリー）を使用することを考えました。これがこの問題の正しいデータ構造であると思いますが、2つの単語がk文字を超える部分があるため、この問題にどのように適応させることができるかわかりません。同じグループに同じものがないので、私は混乱します。私のアイデアの複雑さはO（N * N * K）であり、N<=10,000およびK<=100であることを考えると、このアイデアは十分に高速ではないと思います。私の考えを説明したいと思いますが、私でもまだはっきりしておらず、正しいかどうかさえわからないので、この部分はスキップします。

私の質問は、より高速なアルゴリズムを使用してこの問題を解決できる方法があるかどうかです。そのようなアルゴリズムがある場合は、少し説明してください。よろしくお願いします。文法上の間違いや、問題を明確に説明しなかった場合は申し訳ありません。

4

1 に答える 1

1

まず、最初の k 文字と最後の k 文字を共有するすべての単語をグループ化します。先頭と末尾が異なる 2 つの単語が同じ解になることはあり得ないため、最大のグループはこれらのグループのいずれかに収まる必要があります。

したがって、これらの各グループ (先頭と末尾で同じ k 文字を共有する単語のグループ) 内で、k+1 番目の文字も k+1 番目の文字も共有しない単語の最大セットを見つける必要があります。最後から ' 番目の文字。

頂点がこれらのグループのいずれかの単語の両端から (k+1) の文字のペアであり (重複除去)、エッジが (a, b) と (c, d) の間に発生するグラフを作成します。 =c または b=d。

エッジのないこのサブグラフを見つける必要があります。この削減された問題は、NP 困難な「最大独立部分グラフ」問題のインスタンスであるため、検索を使用して、与えられた単語のセットがあまり厄介でないことを期待して解決する必要があります。おそらく、ここのグラフにはより高速なソリューションを提供する何かがあるのでしょうが、私にはわかりません。

問題全体の解決策は、上記の削減された問題の 1 つに対する最大の解決策です。

お役に立てれば！

于 2012-05-17T14:42:18.510 に答える