-1

重複の可能性：
最速の部分文字列検索アルゴリズムは何ですか？

C ++またはJavaで100,000文字の長さのより大きな文字列に文字列が存在するかどうかを確認するにはどうすればよいですか？

私は方法を知ってstr.find("sub_string");いますが、そのような大きな文字列を処理することはできません。最大実行時間は1秒です。

また、私が探す必要のあるサブ文字列は50,000になる可能性があります。

4

4 に答える 4

5

CまたはC++では、malloc100,000バイトのチャンクを取得するために使用できます。データを入力します。干し草の山から針を見つけるには、次のコードを使用できます。

void *mem_mem(void *haystack, int haystack_len, void *needle, int needle_len)
{
  const char *begin;
  const char *const last_possible
    = (const char *) haystack + haystack_len - needle_len;

  if (needle_len == 0)
    return (void *) &((const char *) haystack)[needle_len - 1];

  for (begin = (const char *) haystack; begin <= last_possible; ++begin)
    if (begin[0] == ((const char *) needle)[0] &&
    !memcmp ((const void *) &begin[1],
         (const void *) ((const char *) needle + 1),
         needle_len - 1))
      return (void *) begin;

  return NULL;
}

かなり最新のプラットフォームでは、これにより、ほんの一瞬で100,000バイトのサブストリングが検出されます。char *型を簡単に使用するように変更できます。同じ干し草の山で複数の検索を行う場合は、干し草の山の長さを1回だけ計算してみてください。strlen必要のないときは電話しないでください。

干し草の山に針の最初の文字が何度も繰り返されている場合、これはひどく最適ではありません。たとえば、「aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaqaaaa ..」で「ab」を検索すると（さらに悪いことに、「abababababababab ... abc ...」で「abc」を検索すると）遅くなります。しかし、あなたは私たちが最適な実装を決定するのに十分な詳細を提供していませんでした。

問題のポイントは、可能な限り最高の最悪の場合のパフォーマンスでアルゴリズムを作成することである可能性があります。もしそうなら、これはおそらく「正しい」答えではありません。すべてのaの後に単一のbが続く干し草の山と、すべてのaの後に最後に単一のbが続く針を想像することができます。その場合、このアルゴリズムには非常に長い時間がかかる可能性があります。

于 2012-09-21T18:35:48.430 に答える
4

これは、控えめな第 1 世代 Intel iMac でほぼ瞬時 (4 ミリ秒) に完了します。Java が逆方向に検索する場合に備えて、100,000 文字の 2 つのブロックの間に検索文字列を配置します。

StringBuilder builder = new StringBuilder();
for (int i = 0; i < 100000; i++) {
    builder.append((char) i);
}
builder.append("sub_string");
for (int i = 0; i < 100000; i++) {
    builder.append((char) i);
}
String maxString = builder.toString();
long t1 = System.currentTimeMillis();
System.out.println(maxString.contains("sub_string"));
long t2 = System.currentTimeMillis();
System.out.println(t2 - t1);

出力

true
4
于 2012-09-21T18:33:42.300 に答える
1

javaを想定：

String.contains("stringtofind");

文字列が別の文字列javadocに存在するかどうかを確認する1つの方法です。

于 2012-09-21T18:29:30.157 に答える
1

文字列コンテンツを見つけるJava 3つの方法。

String.contains("charSequence");
String.contentEquals("charSequence");
String.contentEquals("StringBuffer");

また、Java 仕様により、最大長Integer.MAX_VALUE(常に)の文字列を取得できます。2147483647 (2^31 - 1)

于 2012-09-21T18:31:51.650 に答える