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

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

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

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

Подсказка для второй части: Шаг 1: Для первой строки введите подстроки в хэш-набор. Шаг 2: Для второй строки проверьте значения в хэш-наборе.

Примечание (Дополнительно): эта проблема плохо определена. Ввод и проверка строк в хеш-таблице — это O длины строки. Для строки 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)) = О (п ^ 2)

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

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

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

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

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

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

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

Я не знаю, как они думают, что вы должны использовать 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;

}

}