LazyString.java - master - hel_bumer/Hash

LazyString.java
116 строк6 KB
hel_bumer
Dz_hash
31 янв 2026, 11:07
31 янв 2026, 11:074e157a7
import java.util.HashSet;
import java.util.Set;

public class LazyString {
//    Через конструктор public LazyString(String source, int start, int end),
//    который запоминает нужное место и считает и запоминает хеш подстроки
//            (тк этому подсчёту придётся перебрать символы подстроки,
//             то создание через этот конструктор является линейным).
//    Через вызов метода public LazyString shiftRight(), который вернёт подстроку,
//    соседнюю на один шаг вправо от той, у кого вы вызвали этот метод. Такое создание
//    будет за O(1), тк нам нужно будет лишь сдвинуть границы подстроки который мы запоминаем и
//    пересчитать хеш на основе хеша предыдущей строки, для чего достаточно лишь вычесть
//    код выпавшего символа и прибавить код нового символа.
    private String source; // ссылка на исходную строку
    private int start, end; // границы нашей подстроки
    private int hash; // запоминаем хеш чтобы не пересчитывать

    private LazyString() {}

    public LazyString(String source, int start, int end) {
        this.source = source;
        this.start = start;
        this.end = end;

        // ВАШ КОД
        // а тут нужно посчитать hash
        // просто сложите все коды символов нашей подстроки
        // и сохраните в поле hash.
        // из-за этого, создание LazyString через конструктор будет линейным

        this.hash = 0;
        for (int i = start; i < end; i++) {
            this.hash += source.charAt(i);

        }

    }

    public LazyString shiftRight() {
        // Это способ создания новой LazyString через предыдущую, работает за О(1)
        LazyString shifted = new LazyString();
        shifted.source = source;
        shifted.start = start + 1;
        shifted.end = end + 1;


        // ВАШ КОД
        // Вычислите хеш для shifted из хеша для исходной строки
        // и заполните его в shifted.hash.
        // Заметьте, что достаточно просто вычесть код того
        // символа, что исчез и прибавить код того символа, что
        // появился
        shifted.hash=this.hash-source.charAt(start)+source.charAt(end);

        return shifted;
    }

    public int length() {
        return end - start;
    }

    public boolean equals(LazyString that) {
        // если не равны по длине, то не равны и вовсе
        if (length() != that.length()) {
            return false;
        }

        // перебираем и сравниваем на равенство все символы
        for (int i = 0; i < length(); i++) {
            char myChar = source.charAt(start + i);
            char thatChar = source.charAt(that.start + i);
            if (myChar != thatChar) { // если хотя бы один не совпал, то не равны
                return false;
            }
        }
        return true;
    }

    @Override
    public int hashCode() {
        return hash; // хеш у нас всегда предпосчитан для каждого объекта, чтобы не тратить на это время
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        LazyString that = (LazyString) o;
        return this.equals(that);
    }
    public static boolean hasRepeats(String source, int size) {
        Set<LazyString> slices = new HashSet<>(); // множество всех подстрок длины size
        LazyString prev = null; // переменная для сохранения предыдущей подстроки
        for (int i = 0; i <= source.length() - size; i++) { // перебор всех мест старта подстроки
            LazyString slice; // вырезание подстроки
            if (prev == null) {
                // первую подстроку создаём конструктором за линейную асимптотику
                // ВАШ КОД
                slice = new LazyString(source, i, i + size);
            } else {
                // все остальные через сдвиг вправо от предыдущей подстроки, за O(1)
                // ВАШ КОД
                slice = prev.shiftRight();
            }
            if (slices.contains(slice)) { // проверка на наличие повтора этой подстроки
                return true; // если уже встречали, значит повторы нет
            } else {
                slices.add(slice);  // иначе запоминаем подстроку и перебираем дальше
            }
            prev = slice; // не забываем обновить переменную для предыдущей подстроки для следующей итерации цикла
        }
        return false; // если бы нашли, то вышли бы по return true, а значит повторов нет
    }


}