пересечение двух строк с использованием Java HashSet

Question

Я пытаюсь изучить Java, выполнив некоторые задания из класса Stanford, и у меня возникли проблемы с ответом на этот вопрос.

булева stringIntersect (Строка, String б, внутр длина): Дана 2 строки, рассмотреть все подстроки внутри них длиной LEN. Возвращает true, если в есть такие подстроки, которые появляются в обеих строках. Вычислите это в O (n) раз, используя HashSet.

Я не могу понять, как это сделать, используя 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

Я не уверен, я понимаю, что вы означает, что «вы не можете хранить повторяющиеся символы». hashset - это Set, поэтому он может делать две вещи: вы можете добавить к нему значение, и вы можете добавить к нему значения, и вы можете проверить, уже ли это значение. В этом случае проблема требует ответа на вопрос, сохраняя в HashSet строки, а не символы. Для этого в Java:

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

Попробуйте разбить эту задачу на две части: 1. Сформировать все подстроки длины len строки 2. Используйте это, чтобы решить эту проблему.

Подсказка для второй части является следующим: Шаг 1: Для первой строки введите подстроки в HashSet Шаг 2: Для второй строки, проверьте значения в HashSet

Примечание (Advanced): этот проблема плохо указана. Ввод и проверка строк в хэш-таблице - это длина строки. Для строки a длины n вы имеете подстроки O (n-k) длины k. Таким образом, для string a, являющегося строкой длины n, а строка b является строкой длины m, у вас есть O((n-k)*k+(m-k)*k), это не очень большой О n, так как ваше время работы для k = n/2 равно O ((n/2) * (п/2)) = O (N^2)

---

Edit: Так что, если вы действительно хотите сделать это в O(n) (или, возможно, O(n+m+k))? Я убежден, что первоначальная домашняя работа просила что-то вроде алгоритма, описанного выше. Но мы можем сделать лучше.Более того, мы можем сделать все возможное и по-прежнему сделать решающим инструментом для нашего алгоритма HashSet. Идея состоит в том, чтобы выполнить наш поиск, используя «Rolling Hash». Википедия описывает пару: http://en.wikipedia.org/wiki/Rolling_hash, но мы будем реализовывать свои собственные.

Простым решением будет XOR значения хэшей символов. Это может позволить нам добавить новый символ в хэш-код O(1) и удалить один O(1), вычисляя следующий хэш тривиально. Но этот простой алгоритм не будет работать по двум причинам

1. Хеши символов могут не обеспечивать достаточную энтропию. Хорошо, мы не знаем, будет ли у нас эта проблема, но разрешаем ее в любом случае, просто для удовольствия.
2. Мы хэширование перестановок то же значение ... «а» не должны иметь один и тот же хэш, как «СВ»

Для решения первой задачи мы можем использовать идею с ИИ, а именно позволяет сталь от 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. Это не так сложно перевести.

Вторая проблема также может быть решена. Во-первых, вместо того, чтобы использовать чистый 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 
} 

Okay, чтобы сделать функцию хэширования прокатки, мы просто должны 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), но это выполняется только в том случае, если мы избегаем хэш-коллизий. По-прежнему требуется O(n), чтобы узнать, равны ли две строки. Этот случайный подход работает очень хорошо, и вы можете увеличить размер случайных бит-массивов, чтобы он работал лучше, но он не имеет гарантированной производительности.

Answer 2

Нельзя хранить символы в Hashset, но подстроки.

При рассмотрении строки «hoopla»: если вы сохраняете подстроки «hoop» и «oopla» в Hashset (линейная операция), то она снова линейна, чтобы найти, соответствует ли одна из подстрок «loopla».

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; 

} 

}