2. Алгоритм Рабина – Карпа


Презентация изнутри:

Слайд 0

2. Алгоритм Рабина – Карпа 2 3 2 3 3 2 4 3 2 3 1 5 3 3 2 4 2 3 3 2 2 5 1 Функция: = 11 Число сравнений символов: 0 + 3 + 0 + 0 + 0 + 1 + 0 + 0 + 1 + 0 + 0 + 0 + 0 + 4 = 9 Значения функции на подстроках: 10 11 10 12 12 11 12 9 11 12 12 13 12 11


Слайд 1

public static int RabinKarp(String where, String what) { int n = where.length(); // Длина строки, в которой происходит поиск int m = what.length(); // Длина подстроки long h = 1; // Вычисляемый числовой показатель вытесняемой буквы for (int k = 1; k <= m-1; k++) { h <<= 8; h %= q; } long p = 0; // Числовой показатель подстроки - вычисляется один раз long t = 0; // Изменяемый числовой показатель участка исходной строки for (int k = 0; k < m; k++) { p = ((p << 8) | (byte) what.charAt(k)) % q; t = ((t << 8) | (byte) where.charAt(k)) % q; } // Внешний цикл по исходной строке extLoop: for (int i = 0; i <= n-m; i++) { if (p == t) { // Показатели строк совпали; проверяем, не холостое ли это срабатывание for (int j = 0; j < m; j++) { if (where.charAt(i+j) != what.charAt(j)) { // символы не совпали - продолжаем поиск continue extLoop; } } // подстрока найдена! return i; } else if (i < n-m) { // сдвиг по исходной строке t = (((t - h * (byte) where.charAt(i)) << 8) | (byte) where.charAt(i+m)) % q; } } return -1; }


×

HTML:





Ссылка: