Алгоритмы поиска подстроки в строке - презентация, доклад, проект скачать

Нажмите для полного просмотра!

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Алгоритмы поиска подстроки в строке. Доклад-сообщение содержит 7 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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; // подстрока не найдена }

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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