Алгоритмы поиска подстроки в строке 1. «Наивный» алгоритм оба обобрали обои бобра обои Число сравнений символов: = 24 public static int simpleSearch(String where, String what) { int n = where.length(); int m = what.length(); extLoop: // Внешний цикл поиска в исходной строке for (int i = 0; i <= n-m; i++) { // Внутренний цикл сравнения: for (int j = 0; j < m; j++) { if (where.charAt(i+j) != what.charAt(j)) continue extLoop; } return i; } return -1; } Худший случай: simpleSearch("aaaaaaaaaaaaaaaaaaaaaaaaaaaab", "aaaaaaab");

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

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. Алгоритм Кнута – Морриса – Пратта оба обобрали обои бобра обои 0010 обра 0001 кода 0101 бра 234

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. Алгоритм Бойера - Мура оба одобрили обои бобра обои оби 4424 лор 414 Число сравнений символов: = 10

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; }

Задачи 1. Привести пример строки, для которой поиск подстроки « aaabaaa » будет более эффективным, если делать его методом Кнута – Морриса – Пратта, чем если делать его методом Бойера – Мура. И наоборот. 2.Объясните, как влияет размер таблицы кодов в методе Бойера – Мура на скорость поиска. 3. Что такое «холостое срабатывание» в алгоритме поиска подстроки Робина – Карпа?