Поиск подстрок

Август 9, 2022

Главная
Информатика
Поиск подстрок

Содержание

2. Постановка задачи Есть образец и строка, надо определить индекс, начиная с которого образец содержится в строке.
3. Пример Дана последовательность символов x[1]..x[n]. Определить, встречаются ли в ней идущие друг за другом символы "abcd".
4. Простой алгоритм Решение. Имеется примерно n (если быть точным, n-3) позиций, на которых может находиться искомое
5. Конечные автоматы при чтении слова x слева направо мы в каждый момент находимся в одном из
6. Конечные автоматы Читая очередную букву, мы переходим в следующее состояние по правилу:
7. Алгоритм состояние буква состояние 0 a 1 0 кроме a 0 1 b 2 1 a
8. Фрагмент программы-1 i=1; state=0; {i - первая непрочитанная буква, state - состояние} while ((i n+1) and
9. Фрагмент программы-2 else { state= 0; } }else if (state == 1) { if (x[i] ==
10. Фрагмент программы-3 { state= 0; } }else if (state == 2) { if (x[i] == ‘c’)
11. Фрагмент программы-4 } else if (state == 3) { if( x[i] == ‘d’){ state= 4; }
12. Усовершенствованный алгоритм Надо написать программу, которая ищет произвольный образец в произвольном слове. Это можно делать в
13. Алгоритм Кнута - Морриса – Пратта (КМП) Работает за время O(m+n), где m – длина образца,
14. КМП Длина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки. Префикс –функция заданного образца
15. π-функция Алгоритм вычисления Символы строк нумеруются с 1. Пусть π(S,i) = k. Попробуем вычислить префикс-функцию для
16. π-функция При S[i + 1] = S[k + 1] — положить π(S,i + 1) = k
17. Пример Для строки 'abcdabscabcdabia' вычисление будет таким: 'a'!='b' => π=0;(длина строки 2; строка ab ) 'a'!='c'
18. Пример 'a'=='a' => π=π+1=1; (длина строки 8; строка abcdаbsса) 'b'=='b' => π=π+1=2; (длина строки 9; строка
19. Пример реализации
20. Алгоритм с использованием префикс-функции Пусть ищется строка S1 в строке S2. Построим строку S= S1$S2, где
22. Скачать презентацию

Слайд 2

Постановка задачи
Есть образец и строка, надо определить индекс, начиная с которого

образец содержится в строке. Если не содержится — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число).
При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.

Слайд 3

Пример
Дана последовательность символов x[1]..x[n]. Определить, встречаются ли в ней идущие друг

за другом символы "abcd". (Другими словами, требуется выяснить, есть ли в слове x[1]..x[n] подслово "abcd".)

Слайд 4

Простой алгоритм
Решение. Имеется примерно n (если быть точным, n-3) позиций, на

которых может находиться искомое подслово в исходном слове. Для каждой из позиций можно проверить, действительно ли с нее начинается подслово, сравнив четыре символа. Но обычно слово x[1]..x[n] просматривается слева направо, до появления буквы 'a'. Как только она появилась, ищем за ней букву 'b', затем 'c', и, наконец, 'd'. Если ожидания оправдываются, то слово "abcd" обнаружено. Если же какая-то из нужных букв не появляется, начинаем поиск с новой позиции.

Слайд 5

Конечные автоматы
при чтении слова x слева направо мы в каждый момент

находимся в одном из следующих состояний:
"начальное" (0), "сразу после a" (1),
"сразу после ab" (2),
"сразу после abc" (3) и "сразу после abcd" (4). Читая очередную букву, мы переходим в следующее состояние по правилу

Слайд 6

Конечные автоматы
Читая очередную букву, мы переходим в следующее состояние по правилу:
<Текущее состояние>

<Очередная буква> <Новое состояние >

Слайд 7

Алгоритм
состояние буква состояние 0 a 1 0 кроме a 0 1 b 2 1 a

1 1 кроме a,b 0 2 c 3 2 a 1 2 кроме a,c 0 3 d 4 3 a 1 3 кроме a,d 0
Состояние 4 - конечное

Слайд 8

Фрагмент программы-1
i=1; state=0; {i - первая непрочитанная буква, state - состояние} while ((i

<> n+1) and (state <> 4)) { if (state = =0) { if( x[i] ==‘a’) { state= 1; }

Слайд 9

Фрагмент программы-2
else { state= 0; } }else if (state == 1) { if (x[i] ==

‘b’) { state= 2; } else if( x[i] == ‘a’) { state= 1; }else

Слайд 10

Фрагмент программы-3
{ state= 0; } }else if (state == 2) { if (x[i] == ‘c’)

{ state= 3; }else if (x[i] == ‘a’){ state= 1; } else { state= 0; }

Слайд 11

Фрагмент программы-4
} else if (state == 3) { if( x[i] == ‘d’){ state=

4; } else if (x[i] == ‘a’){
state= 1; } else { state= 0; } } } answer = (state == 4);

Слайд 12

Усовершенствованный алгоритм
Надо написать программу, которая ищет произвольный образец в произвольном

слове. Это можно делать в два этапа:
1. сначала по образцу строится таблица переходов конечного автомата
2. читается входное слово и состояние преобразуется в соответствии с этой таблицей

Слайд 13

Алгоритм Кнута - Морриса – Пратта (КМП)
Работает за время O(m+n), где

m – длина образца, n – длина текста
Для произвольного слова X рассмотрим все его начала (префиксы), одновременно являющиеся его концами (суффиксами), и выберем из них самое длинное
Примеры: l(aba)=a, l(abab)=ab, l(ababa)=aba, l(abc) = пустое слово.

Слайд 14

КМП
Длина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки.
Префикс –функция заданного

образца несет информацию о том, где в образце повторно встречаются различные префиксы образца. Использование этой информации позволяет избежать проверки заведомо недопустимых сдвигов.

Слайд 15

π-функция
Алгоритм вычисления
Символы строк нумеруются с 1.
Пусть π(S,i) = k. Попробуем вычислить префикс-функцию для i +

1.
Если S[i + 1] = S[k + 1], то, естественно, π(S,i + 1) = k + 1. Если нет — пробуем меньшие суффиксы. Очевидно, что также будет суффиксом строки, а для любого строка суффиксом не будет. Таким образом, получается алгоритм:

Слайд 16

π-функция
При S[i + 1] = S[k + 1] — положить π(S,i + 1) = k + 1.
Иначе при k = 0 — положить π(S,i +

1) = 0.
Иначе — установить k: = π(S,k), GOTO 1.

Слайд 17

Пример
Для строки 'abcdabscabcdabia' вычисление будет таким:
'a'!='b' => π=0;(длина строки 2; строка ab )
'a'!='c'

=> π=0; (длина строки 3; строка abс )
'a'!='d' => π=0;(длина строки 4; строка abcd)
'a'=='a' => π=π+1=1; (длина строки 5; строка abcdа)
'b'=='b' => π=π+1=2;(длина строки 6; строка abcdаb)
'c'!='s' => π=0; (длина строки 6; строка abcdаbs)
'a'!='c' => π=0; (длина строки 7; строка abcdаbsс)

Слайд 18

Пример
'a'=='a' => π=π+1=1; (длина строки 8; строка abcdаbsса)
'b'=='b' => π=π+1=2; (длина

строки 9; строка abcdаbsсаb)
'c'=='c' => π=π+1=3; (длина строки 9; строка abcdаbsсаbс)
'd'=='d' => π=π+1=4;(длина строки 10; строка abcdаbsсаbсd)
'a'=='a' => π=π+1=5; (длина строки 10; строка abcdаbsсаbсdа)
'b'=='b' => π=π+1=6; (длина строки 11; строка abcdаbsсаbсdаb)
‘s'!='i' => π=0; (длина строки 12; строка abcdаbsсаbсdаbi)
'a'=='a' => π=π+1=1; (длина строки 13; строка abcdаbsсаbсdаbiа)

Слайд 19

Пример реализации

Слайд 20

Алгоритм с использованием префикс-функции
Пусть ищется строка S1 в строке S2. Построим

строку S= S1$S2, где $ — символ, не встречающийся ни в S1, ни в S2. Далее вычислим значения префикс-функции от строки S и всех её префиксов. Теперь, если префикс-функция от префикса строки S длины i равна n, где n—длина S1, и i>n, то в строке S2есть вхождение S1, начиная с позиции i-2n.

Поиск подстрок

Содержание

Постановка задачи Есть образец и строка, надо определить индекс, начиная с которого

ПримерДана последовательность символов x[1]..x[n]. Определить, встречаются ли в ней идущие друг

Простой алгоритмРешение. Имеется примерно n (если быть точным, n-3) позиций, на

Конечные автоматыпри чтении слова x слева направо мы в каждый момент

Конечные автоматыЧитая очередную букву, мы переходим в следующее состояние по правилу:<Текущее состояние>

Алгоритмсостояние буква состояние 0 a 1 0 кроме a 0 1 b 2 1 a

Фрагмент программы-1i=1; state=0; {i - первая непрочитанная буква, state - состояние} while ((i

Фрагмент программы-2else { state= 0; } }else if (state == 1) { if (x[i] ==

Фрагмент программы-3{ state= 0; } }else if (state == 2) { if (x[i] == ‘c’)

Фрагмент программы-4} else if (state == 3) { if( x[i] == ‘d’){ state=

Усовершенствованный алгоритм Надо написать программу, которая ищет произвольный образец в произвольном

Алгоритм Кнута - Морриса – Пратта (КМП)Работает за время O(m+n), где

КМПДлина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки.Префикс –функция заданного

π-функцияАлгоритм вычисленияСимволы строк нумеруются с 1.Пусть π(S,i) = k. Попробуем вычислить префикс-функцию для i +

π-функцияПри S[i + 1] = S[k + 1] — положить π(S,i + 1) = k + 1.Иначе при k = 0 — положить π(S,i +

ПримерДля строки 'abcdabscabcdabia' вычисление будет таким:'a'!='b' => π=0;(длина строки 2; строка ab ) 'a'!='c'

Пример'a'=='a' => π=π+1=1; (длина строки 8; строка abcdаbsса)'b'=='b' => π=π+1=2; (длина