Содержание
- 2. 2. Алгоритм Рабина – Карпа 2 3 2 3 3 2 4 3 2 3 1
- 3. public static int RabinKarp(String where, String what) { int n = where.length(); // Длина строки, в
- 4. 3. Алгоритм Кнута – Морриса – Пратта о б а о б о б р а
- 5. public static int KnuthMorrisPratt(String where, String what) { int n = where.length(); // Длина строки, в
- 6. 4. Алгоритм Бойера - Мура о б а о д о б р и л и
- 8. Скачать презентацию
Слайд 2
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
+
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
Слайд 3
public static int RabinKarp(String where, String what) {
int n =
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;
}
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;
}
Слайд 4
3. Алгоритм Кнута – Морриса – Пратта
о
б
а
о
б
о
б
р
а
л
и
о
б
о
и
б
о
б
р
а
3. Алгоритм Кнута – Морриса – Пратта
о
б
а
о
б
о
б
р
а
л
и
о
б
о
и
б
о
б
р
а
Слайд 5
public static int KnuthMorrisPratt(String where, String what) {
int n =
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; // подстрока не найдена
}
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. Алгоритм Бойера - Мура
о
б
а
о
д
о
б
р
и
л
и
о
б
о
и
б
о
б
р
а
а
б
и
4
4
2
4
л
о
р
4
1
4
Число сравнений символов:
1
+
4. Алгоритм Бойера - Мура
о
б
а
о
д
о
б
р
и
л
и
о
б
о
и
б
о
б
р
а
а
б
и
4
4
2
4
л
о
р
4
1
4
Число сравнений символов:
1
+
1
+ 2
+ 1
+ 1
+ 4
= 10
Следующая -
Православный храм