Java HashSetを使用した2つの文字列の交差

Question

私はスタンフォードクラスから割り当てを行ってJavaを学習しようとしていますが、この質問に答えるのが難しいです。

ブールstringIntersect（文字列、列B、int型のLEN）：2列、 は長さlenのその内のすべてのサブストリングを考える考えます。 両方の文字列にそのような部分文字列がある場合はtrueを返します。 これをO（n）時間で計算するには、HashSetを使用します。

繰り返し文字を保存することができないため、ハッシュセットを使用して行う方法を理解できません。したがって、stringIntersect(hoopla, loopla, 5)はtrueを返す必要があります。

ありがとうございました！

編集：すべてのあなたの迅速な対応に感謝します。説明だけでなく説明も見ておくと便利でした。ハッシュセットに部分文字列を格納すると、アルゴリズムがより効率的になる理由がわかりません。

public static boolean stringIntersect(String a, String b, int len) { 
    assert (len>=1); 
    if (len>a.length() || len>b.length()) return false; 
    String s1=new String(),s2=new String(); 
    if (a.length()<b.length()){ 
     s1=a; 
     s2=b; 
    } 
    else { 
     s1=b; 
     s2=a; 
    } 
    int index = 0; 
    while (index<=s1.length()-len){ 
     if (s2.contains(s1.substring(index,index+len)))return true; 
     index++; 
    } 
    return false; 
} 

Answer 1

を私は何を理解していません「繰り返しの文字を格納することはできません」という意味です。ハッシュセットはSetなので、2つのことができます。値を追加したり、値を追加したりできます。この場合、問題は文字列ではなく文字列をHashSetに格納して質問に答えることを望みます。 Javaでこれを行うには：

Set<String> stringSet = new HashSet<String>(); 

は二つの部分にこの問題を破壊してみてください。 1は、この問題を解決するために、文字列 2.の長さlenのすべての部分文字列を生成します。

部2のヒントがある： ステップ1：最初の文字列の場合HashSetの ステップ2にサブストリングを入力します。この：2番目の文字列については、HashSetの

注（高度）の値をチェック問題はあまり指定されていません。ハッシュテーブルに文字列を入力してチェックするのは、文字列の長さです。長さnの文字列aには、長さkのO（n-k）個の部分文字列があります。だからstring aは長さがnの文字列で、文字列bは長さがmの文字列ですO((n-k)*k+(m-k)*k)これはk = n/2の実行時間がO（（n/2）*であるため、 N/2））= O（N^2）

---

編集：だから、あなたが実際にO(n)（あるいはO(n+m+k)でこれを行うために何をしたい場合）？私の考えは、元の宿題が上記のアルゴリズムのようなものを求めていたことです。しかし、私たちはより良くすることができます。さらに、私たちはもっとうまくやっても、HashSetをアルゴリズムの重要なツールにすることができます。このアイデアは、 "Rolling Hash"を使って検索を実行することです。 Wikipediaはカップルについて説明しています：http://en.wikipedia.org/wiki/Rolling_hashでも、私たちは自分自身を実装します。

簡単な解決策を一緒にハッシュ文字の値をXORすることであろう。これにより、新しい文字をハッシュO(1)に追加し、O(1)を削除して次のハッシュを計算しやすくすることができます。しかし、この単純なアルゴリズムは2つの理由で機能しません。

1. 文字ハッシュは十分なエントロピーを提供しません。さて、私たちがこの問題を抱えているかどうかはわかりませんが、とにかく楽しいために解決してください。
2. 私たちは、同じ値に順列をハッシュしますが...「ABC」

たちはAIからのアイデアを使用することができます最初の問題を解決するには、「CBA」と同じハッシュを持つべきではない、すなわちから鋼をすることができますZobrist hashing。考えられるすべての文字に、より大きな長さのランダムな値を割り当てることです。 ASCIを使用していた場合、すべてのASCI文字を含む配列を簡単に作成できますが、Unicode文字を使用すると問題が発生します。代わりに値を遅延的に割り当てることです。

object LazyCharHash{ 
    private val map = HashMap.empty[Char,Int] 
    private val r = new Random 
    def lHash(c: Char): Int = { 
    val d = map.get(c) 
    d match { 
     case None => { 
     map.put(c,r.nextInt) 
     lHash(c) 
     } 
     case Some(v) => v 
    } 
    } 
} 

これはScalaコードです。 ScalaはJavaよりもあまり冗長ではありませんが、Javaコレクションを使用できるようになりました。そのため、命令型のScalaを使用していきます。翻訳が難しいことではありません。

第二の問題は、aswellを解決することができます。まず、代わりに純粋なXORを使用して、我々はこのようにハッシュ関数は今、シフトで私たちのXORを組み合わせ：のコース

def fullHash(s: String) = { 
    var h = 0 
    for(i <- 0 until s.length){ 
    h = h >>> 1 
    h = h^LazyCharHash.lHash(s.charAt(i)) 
    } 
    h 
} 

、文句を言わないパフォーマンス上の利点を与えるfullHashを使用します。それは、私たちは（私たちはそれを使用すると約束）HashSetに値を格納するために、当社のハッシュ関数を使用する方法を必要なだけの仕様

です。私達はちょうどラッパークラスを作成することができます。

class HString(hash: Int, string: String){ 
    def getHash = hash 
    def getString = string 
    override def equals(otherHString: Any): Boolean = { 
    otherHString match { 
     case other: HString => (hash == other.getHash) && (string == other.getString) 
     case _ => false 
    } 
    } 
    override def hashCode = hash 
} 

オーケーを、ハッシュ関数のローリングを作るために、私達はちょうど私たちはもはや使用される文字に関連付けられた値をXORする必要があります。それには、その価値を適切な額だけシフトさせるだけです。

def stringIntersect(a: String, b: String, len: Int): Boolean = { 
    val stringSet = new HashSet[HString]() 
    var h = 0 
    for(i <- 0 until len){ 
    h = h >>> 1 
    h = h^LazyCharHash.lHash(a.charAt(i)) 
    } 
    stringSet.add(new HString(h,a.substring(0,len))) 
    for(i <- len until a.length){ 
    h = h >>> 1 
    h = h^(LazyCharHash.lHash(a.charAt(i - len)) >>> (len)) 
    h = h^LazyCharHash.lHash(a.charAt(i)) 
    stringSet.add(new HString(h,a.substring(i - len + 1,i + 1))) 
    } 
    ... 

このコードを自分で完成させる方法を知ることができます。

このO(n)ですか？まあ、それは何を意味するのか。ビッグオハイオ州、ビッグオメガ、ビッグシータ、すべての境界線のメトリックです。アルゴリズムの最悪の場合、最良の場合、または何か他のもののメトリックとして役立つ可能性があります。この場合、これらの変更は、がO(n)パフォーマンスが期待できますが、我々はハッシュの衝突を避ける場合にのみ成立します。 2つの文字列が等しいかどうかを調べるにはまだO(n)が必要です。このランダムアプローチはうまくいきますし、ランダムビット配列のサイズを拡大してよりうまくいくようにすることもできますが、パフォーマンスは保証されていません。

Answer 2

あなたは保存しないでくださいHashSetの中の文字が、ストリング：私はもともとのような解決策を持っていました。

文字列 "hoopla"を考慮する：ハッシュセット（線形演算）に部分文字列 "hoopl"と "oopla"を格納すると、 "loopla"の部分文字列の1つが一致するかどうかを再度調べます。

Answer 3

私は、彼らはあなたがHashSetのを使うことになっている考えているかわからないが、私はこのようなソリューションやってしまった：

public class StringComparator { 

    public static boolean compare(String a, String b, int len) { 

    Set<String> pieces = new HashSet<String>(); 

    for (int x = 0; (x + len) <= b.length(); x++) { 
     pieces.add(a.substring(x, x + len )); 
    } 

    for (String piece : pieces) { 
     if (b.contains(piece)) { 
      return true; 
     } 
    } 

    return false; 

} 

}