Я не уверен, что понимаю, что вы подразумеваете под «вы не можете хранить повторяющиеся символы». Хэш-набор - это Set, поэтому он может выполнять две функции: вы можете добавлять к нему значения и добавлять к нему значения, и вы можете проверить, если значение уже в нем.В этом случае проблема требует, чтобы вы ответили на вопрос, храня в HashSet строки, а не символы.Чтобы сделать это в Java:
Set<String> stringSet = new HashSet<String>();
Попробуйте разбить эту проблему на две части: 1. Сгенерируйте все подстроки длины len строки 2. Используйте это для решения проблемы.
Подсказка для второй части: Шаг 1. Для первой строки введите подстроки в хэш-набор. Шаг 2. Для второй строки проверьте значения в хэш-наборе
Примечание (Дополнительно): эта проблемаплохо указано.Ввод и проверка строк в хеш-таблице - это длина строки.Для строки a длины n у вас есть O (nk) подстрок длины k.Таким образом, для string a, являющейся строкой длины n, и для строки b, являющейся строкой длины m, у вас есть O((n-k)*k+(m-k)*k), это не очень большое значение Oh n, поскольку время выполнения для k = n / 2 равно O((n / 2) * (n / 2)) = O (n ^ 2)
Редактировать: Так что, если вы действительно хотите сделать это в O(n) (или, возможно, O(n+m+k)))?Я считаю, что оригинальная домашняя работа требовала чего-то вроде алгоритма, который я описал выше.Но мы можем сделать лучше.Более того, мы можем добиться большего успеха и все же сделать HashSet важнейшим инструментом для нашего алгоритма.Идея состоит в том, чтобы выполнить наш поиск, используя «Rolling Hash».Википедия описывает пару: http://en.wikipedia.org/wiki/Rolling_hash,, но мы реализуем нашу собственную.
Простым решением будет XOR значений хэшей символов вместе.Это может позволить нам добавить новый символ в хэш O(1) и удалить один O(1), что сделает вычисление следующего хеша тривиальным.Но этот простой алгоритм не будет работать по двум причинам:
- Хеши символов могут не обеспечивать достаточную энтропию.Хорошо, мы не знаем, возникнет ли у нас эта проблема, но давайте все равно решим ее, просто для удовольствия.
- Мы будем хешировать перестановки с тем же значением ... "abc" не должен иметь тот же хеш, что и "cba "
Чтобы решить первую проблему, мы можем использовать идею AI, а именно: сталь из Зобристское хеширование .Идея состоит в том, чтобы назначить каждому возможному символу случайное значение большей длины.Если бы мы использовали 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), чтобы определить, равны ли две строки.Этот случайный подход работает довольно хорошо, и вы можете увеличить размер случайных битовых массивов, чтобы он работал лучше, но он не имеет гарантированной производительности.