Первое что надо сдетать это определить основание P и модуль MODULE.
Это два простых числа, первое маленькое, второе - большое.

private static final int P = 29;
private static final long MODULE = 1_000_000_007L;

Что бы не считать каждый раз степени модуля вычисляем их сразу столько сколько надо:

private static void initPower(int n) {
    power = new long[n + 1];
    power[0] = 1;
    for (int i = 1; i < n + 1; i++) {
        power[i] = (power[i - 1] * P) % MODULE;
    }
}

Тут уже используется модуль.

Теперь считаем и заполняем массив префиксных хэшей для того с чем будем работать:

private static void buildPrefixHashArray(String s) {
    prefixHashArray = new long[s.length() + 1];
    for (int i = 1; i < s.length() + 1; i++) {
        prefixHashArray[i] = (prefixHashArray[i - 1] + (s.charAt(i - 1) - 'a' + 1) * power[i - 1]) % MODULE;
    }
}

Запись "char-'a'+1" тут использована просто для получения порядкового номера символа в алфавите, т.к. в моей задаче строка состоит только из маленьких английских букв. Но использование кода символа тоже работает.

Так же нам понадобится просо вычислять хеш строки:

private static long calculateHash(String s) {
    long hash = 0;
    int p = 0;
    for (char c : s.toCharArray()) {
        hash = (hash + getCharPowerValue(c) * power[p++]) % MODULE;
    }
    return hash;
}

И последнее - надо научится получать хеш подстроки, а это достаточно просто:

private static long getIntervalHash(int startIndex, int finishIndex) {
    long sub = prefixHashArray[finishIndex] - prefixHashArray[startIndex];
    return sub > -1 ? sub : sub + MODULE;
}

Обратите внимание на то, как метод getIntervalHash возвращает ответ - это магия циклических колец. Этот момент я долго не мог понять, а поэтому и не учитывал в коде.

Преимущества использования полиномиальных хешей при сравнении строк заключаются в следующем:

Эффективность:
Полиномиальные хеши позволяют вычислять хеш-коды строки за линейное время и сравнивать их за константное время. Это значительно ускоряет задачу сравнения строк по сравнению с посимвольным сравнением, особенно для длинных строк.

Сравнение подстрок:
Полиномиальные хеши поддерживают эффективное вычисление хешей для подстрок, что полезно в задачах, связанных с поиском подстрок и алгоритмами поиска шаблонов.

Устойчивость к коллизиям:
При правильно выбранных параметрах (в том числе модуле и базе) вероятность коллизий хешей низка. Это делает подход надежным на практике.

Простота реализации:
Алгоритм полиномиального хеширования прост в реализации и может быть легко адаптирован для различных задач, связанных с обработкой строк.

Эти качества делают полиномиальные хеши распространённым выбором для задач, связанных со сравнением строк, таких как текстовые алгоритмы и структуры данных, например, "суффиксные массивы" или "интервалные деревья".

Основные операции

1. Find (Найти):
   Определяет, к какому множеству принадлежит элемент. Это может быть использовано для проверки принадлежности двух элементов одному множеству.

2. Union (Объединить):
   Объединяет два множества в одно.

Основные концепции

• Репрезентатив (Представитель):
  Каждый элемент множества имеет некоторое представительное значение (обычно голову дерева), которое является корнем дерева представления данного множества.

• Ранговое дерево и сжатие путей:
  Используются для оптимизации работы алгоритма. Сжатие путей помогает уменьшить глубину дерева, быстро находя представителя, а ранговое дерево помогает поддерживать низкую высоту дерева при объединении.

Реализация

Реализуем это как отдельную структуру данных, т.е. сделаем отдельный класс

    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        init(size);
    }

    private void init(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

   public int find(int p) {
        if (parent[p] != p) {
            parent[p] = find(parent[p]); // Рекурсивное сжатие путей
        }
        return parent[p];
    }

   public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if (rootP != rootQ) {
            // Объединяем более низкое дерево под более высокое
            if (rank[rootP] > rank[rootQ]) {
                parent[rootQ] = rootP;
            } else if (rank[rootP] < rank[rootQ]) {
                parent[rootP] = rootQ;
            } else {
                parent[rootQ] = rootP;
                rank[rootP]++; // увеличиваем ранг, если высоты равны
            }
        }
    }