Поиск подстроки в строке

[videolord]

Поиск подстроки в строке с помощью хеша
Я нашел очень интересную статью и не могу его реализовать практически на java, или может кто-то пользовался этим алгоритмом
и написал ?

Поиск подстроки в строке - часто возникающая на практике задача. Поиск подстроки в строке обычной подстановкой к каждой позиции строки всей подстроки - метод неэффективный и вообще грустный. Я рассмотрю метод поиска с помощью хеш-функции - достаточно простой и быстрый.

Каждый символ имеет свой уникальный код от 0 до 255. Суть метода заключается в том, чтобы для подстроки подсчитать некоторую хэш-функцию (например сумму кодов всех символов в строке), затем посчитать ту же самую хэш-функцию для части строки, равной по длине подстроке, и, в случае совпадения хэш-функции, полностью сравнить его. Ускорение работы алгоритма связано с тем, что мы каждый раз не пересчитываем каждый раз хэш-функцию, а только отнимаем значение функции от самого "старого" символа и добавляем значение функции от следующего символа.

Пример:

Алфавит кодов:
Q = 1
W = 2
E = 3
R = 4
T = 5
Y = 6

Подстрока: QWERTY
Строка: QWERYTEWEQWERTY

Считаем хэш-функцию для подстроки: SS = 1+2+3+4+5+6+7 = 28

QWERYTEWEQWERTY


Считаем хэш-функцию для первых 6 символов строки: FS = 1+2+3+4+5+7+6 = 28

Проводим полное сравнение строк - строки не совпадают.

QWERYTEWEQWERTY

FS = 28 - [Q] + [E] = 28 - 1 + 3 = 30 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 30 - [W] + [W] = 30 - 2 + 2 = 30 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 30 - [E] + [E] = 30 - 3 + 3 = 30 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 30 - [R] + [Q] = 30 - 4 + 1 = 27 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 27 - [Y] + [W] = 27 - 6 + 2 = 23 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 23 - [T] + [E] = 23 - 5 + 3 = 21 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 21 - [E] + [R] = 21 - 3 + 4 = 22 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 22 - [W] + [T] = 22 - 2 + 5 = 25 - код не совпадает, сравнение не проводим.

QWERYTEWEQWERTY

FS = 25 - [E] + [Y] = 25 - 3 + 6 = 28 - код совпадает, полное сравнение совпадает. Ура
Продолжение здесь http://g6prog.narod.ru/findstr.html

[netrino]

Вот накидал:

class Program {

    static int substring(String string, String subString) {
        if (string.length() < subString.length())
            return -1;

        int patternHash = 0;
        int currentHash = 0;

        for (int i = 0; i < subString.length(); i++) {
            patternHash += subString.charAt(i);
            currentHash += string.charAt(i);
        }

        int end = string.length() - subString.length() + 1;
        for (int i = 0; i < end; i++) {
            if (patternHash == currentHash)
                if (string.regionMatches(i, subString, 0, subString.length()))
                    return i;

            currentHash -= string.charAt(i);
            if (i != end - 1)
                currentHash += string.charAt(i + subString.length());
        }

        return -1;
    }

    public static void main(String[] args) {
        String string = "QWERYTEWEQWERTY";
        String substr = "QWERTY";

        System.out.println("Search result: " + substring(string, substr));
        System.out.println("Ensure result: " + string.indexOf(substr));
    }
}

[videolord]

Классно!!! Спасибо огромное вам netrino!!!