🗊Презентация Алгоритмы поиска подстроки в строке

Алгоритмы поиска подстроки в строке

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

public static int RabinKarp(String where, String what) { 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; }

3. Алгоритм Кнута – Морриса – Пратта

public static int KnuthMorrisPratt(String where, String what) { public static int KnuthMorrisPratt(String where, String what) { int n = where.length(); // Длина строки, в которой происходит поиск int m = what.length(); // Длина подстроки // Формирование таблицы сдвигов int[] table = new int[m]; table[0] = 0; int shift = 0; for (int q = 1; q < m; q++) { while (shift > 0 && what.charAt(shift) != what.charAt(q)) { shift = table[shift-1]; } if (what.charAt(shift) == what.charAt(q)) shift++; table[q] = shift; } // Поиск с использованием таблицы сдвигов shift = 0; for (int i = 0; i < n; i++) { while (shift > 0 && what.charAt(shift) != where.charAt(i)) { shift = table[shift-1]; } if (what.charAt(shift) == where.charAt(i)) shift++; if (shift == m) return i-m+1; // подстрока найдена } return -1; // подстрока не найдена }

4. Алгоритм Бойера - Мура

private static final int shLen = 256; private static final int shLen = 256; private static int hash(char c) { return c & 0xFF; } public static int BoyerMoore(String where, String what) { int n = where.length(); // Длина исходной строки int m = what.length(); // Длина образца // Формирование массива сдвигов int[] shifts = new int[shLen]; // Для символов, отсутствующих в образце, сдвиг равен длине образца for (int i = 0; i < shLen; i++) { shifts[i] = m; } // Для символов из образца сдвиг равен расстоянию от // последнего вхождения символа в образец до конца образца for (int i = 0; i < m-1; i++) { shifts[hash(what.charAt(i))] = m-i-1; } // Поиск с использованием таблицы сдвигов for (int i = 0; i <= n-m; ) { // Сравнение начинается с конца образца for (int j = m-1; j>=0; j--) { if (where.charAt(i+j) == what.charAt(j)) { if (j == 0) return i; } else { break; } } // Сдвиг производится в соответствии с кодом последнего из сравниваемых символов i += shifts[hash(where.charAt(i+m-1))]; } return -1; }