Материал: Вопросы к экзамену

Алгоритм NSM (T[1…n], P[1…m])

1)for S=0 to n-m do;

2)if P[1…m]=T[S+1…S+m] then;

3)printf “подстрока Р входит в Т”. Вычислительная сложность: O((n-m+1)m). Алгоритм КМР для поиска:

Префикс функция ассоциирующаяся с образом Р несет информацию, где в Р встречаются префиксы строки,

использование этой информации не считывает заведомо не подходящие сдвиги.

#Т=bacbababababcbab P=ababaca, сдвиг = 4 T[S+1…S+q]=P[1…q]

Некоторые последующие сдвиги будут недостимыми.

CPF(p[1..m])

1.s[1]←0

2.for q=2 to m do

3.k←s[q-1]

4.while (P[q]≠P[k+1]) and (k>0) do

5.k←s[k]

6.if (P[q]≠P[k+1] and (k=0) then s[q] ←0

7.else s[q] ←k+1

8.end for

9.return s

KMP(T[1..n],P[1..m])

1.s←CPF(P)

2.q←0

3.for k=1 to n do

4.while T[k]≠P

5.q←s[q]

6.if T[k]=P[q+1] then

7.q←q+1

8.if q=m then

9.printf “Образец входит со сдвигом”,k-m

10.q←s[q]

11.end for

6. Поиск подстроки в строке. Алгоритм Бойера-Мура.

Поиск подстроки в строке (String searching algorithm) — класс алгоритмов над строками, которые позволяют найти паттерн (pattern) в тексте (text).

Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.

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

6

Таким образом для сдвига позиции начала сравнения алгоритм Бойера-Мура выбирает между двумя функциями, называемыми эвристиками хорошего суффикса и плохого символа (иногда они называются эвристиками совпавшего суффикса и стоп-символа). Так как функции эвристические, то выбор между ними простой — ищется такое итоговое значение, чтобы мы не

проверяли максимальное число позиций и при этом нашли все подстроки равные шаблону.

( ) −средний случай

( ) −худшийслучай

Code: https://github.com/Markoutte/sandbox/tree/master/src/main/java/me/markoutte/sandbox/algorithms/strings

++++

Использование алгоритма Кнута-Морисса-Пратта в большинстве случаев поиска в обычных текстах весьма незначителен. Метод же, предложенный Р. Боуером и Д. Муром в 1975 г., улучшает обработку самого плохого случая.

БМ-поиск основывается на необычном соображении сравнение символов начинается с конца слова, а не с начала. Как и в случае КМП-поиска, слово перед фактическим поиском трансформируется в некоторую таблицу. Пусть для каждого символа x из алфавита величина dx расстояние от самого правого в слове вхождения x до правого конца слова. Представим себе, что обнаружено расхождение между словом и текстом. В этом случае слово сразу же можно сдвинуть вправо на dpM-1 позиций, т.е. на число позиций, скорее всего большее единицы. Если несовпадающий символ текста в слове вообще не встречается, то сдвиг становится даже больше, а именно сдвигать можно на длину всего слова.

Например, T=ABCABCABFABCABD

P=ABCABD (сравниваем то что подчеркнуто, идем с конца, не совпало D с C, сдвиг =3, чтоб С=С)

ABCABD (не совпало D и F, так как F нет в образце) ABCABD(полное совпадение слово найдено)

CLOF(p[1..m], sum) sum это значок суммы

1.for all a sum do

2.l[a]←0

3.for k=1 to m do

4.l[P[k]] ←k

5.return l

CGSF(p[1..m])

1.s←CPF(P)

2.P’ ← обращение строки P

3.S’ ← CPF(P’)

4.For j=0 to m do

5.Y[j] ←m-s[m]

6.For k=1 to m do

7

7.J ← m-s’[k]

8.Y[j] ← min(y[j],k-s’[k])

9.End for

10.Return y

BM(T[1..n],P[1..m])

1.L ← CLOF(P,m,sum)

2.Y ← CGSF(p,m)

3.S ← 0

4.While S<=n-m do

5.k←m

6.while (k>0) and (P[k]=T[S+k]) do

7.k←k-1

8.if k=0 then

9.printf “Образец со сдвигом”,S

10.s←s+y[0]

11.else s←s+max(y[k],k-y[T[s+k]])

12.end while

7.Линейные структуры данных. Списки. Динамический массив.

Линейные структуры — это упорядоченные структуры, в которых адрес элемента

однозначно определяется его номером.

Линейных структуры данных обладают следующими свойствами:

•Каждый элемент имеет не более 1 предшественника

•Два разных элемента не могут иметь одинакового последователя

Клинейным структурам данным можно отнести:

•Массивы

•Динамические массивы

•Связный список

•Стек

•Очередь

•Дек

•Хэш-таблица

Связный список - это разновидность линейных структур данных, представляющая собой последовательность элементов, обычно отсортированную в соответствии с заданным правилом. Последовательность может содержать любое количество элементов, поскольку при создании списка используется динамическое распределение памяти. Каждый элемент связного списка представляет собой отдельный объект, содержащий поле для хранения информации и указатель наследующийэлементсписка(авслучаедвусвязногоспискавобъектехранитсятакжеуказатель на предыдущий элемент).

Массив – одна из простейших и наиболее широко применяемых в компьютерных программах линейных структур данных. В любом языке программирования массивы имеют несколько общих свойств:

• Содержимое массива хранится в непрерывной области памяти.

8

•Все элементы массива имеют одинаковый тип; поэтому массивы называют однородными структурами данных.

•Существует прямой доступ к элементам массива.

8.Линейные структуры данных. Списки. Связный и двусвязный списки.

См. 7 вопрос.

9.Линейные структуры данных. Очереди. Кольцевые очереди.

См. 7 вопрос. +

Очередь– линейнаяструктураданных,удовлетворяющаяпринципуFIFO(первыйпришел

–первый ушел)

•Поддерживает добавление элемента в конец,

•Поддерживает доступ к первому и последнему элементу,

•Поддерживает удаление первого элемента

•Не поддерживает итераторы

Кольцевая очередь - это идентичная очереди структура данных, с одним отличием, после последнего элемента сразу же снова идет первый. Это можно организовать с помощью указателей(в случае списка), ис помощью операции остатка от деления (%) (вслучае массивов).

10.Линейные структуры данных. Стеки. Деки. Использование стека для решения задачи о правильных скобках.

См. 7 вопрос. +

Дек (deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO, поэтому на ней можно реализовать как стек, так и очередь.

Стек -- линейная структура данных, удовлетворяющая принципу FILO(первый пришел – последний ушел)

•Поддерживает добавление элемента в конец,

•Поддерживает доступ к последнему элементу.

•Поддерживает удаление последнего элемента

Отличным примером использования стека для решения задачи о правильных скобках является обратная польская нотация.

Алгоритм (упращенной реализаиии):

•Пока есть ещё символы для чтения:

•Читаем очередной символ.

•Если символ является открывающей скобкой, помещаем его в стек.

•Если символ является закрывающей скобкой:

До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.

9

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

11. Формы представления выражений. Польская и обратная польская нотации. Алгоритм трансформации инфиксной записи в постфиксную.

Существуют три формы представления выражений: Инфиксные, префиксные и постфиксные.

Инфиксное выражение – это самое обычное и привычное выражение для восприятия человека, когда оператор находится между двумя опрандами (например ''А+ С'').

Префиксная запись выражения требует, чтобы все операторы предшествовали двум операндам, с которыми они работают. Постфиксная, в свою очередь, требует, чтобы операторы шли после соответствующих операндов.

Пример:

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

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

Алгоритм:

•Пока есть ещё символы для чтения:

•Читаем очередной символ.

•Если символ является числом или постфиксной функцией (например, ! — факториал), добавляем его к выходной строке.

•Если символ является префиксной функцией (например, sin — синус), помещаем его в

стек.

•Если символ является открывающей скобкой, помещаем его в стек.

•Если символ является закрывающей скобкой:

До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходнуюстрокунедобавляется.Еслистекзакончилсяраньше,чеммывстретилиоткрывающую скобку, это означает,что в выражении либо неверно поставлен разделитель, либо несогласованы скобки.

•Еслисуществуютразныевидыскобок,появлениенепарнойскобкитакжесвидетельствует об ошибке. Если какие-то скобки одновременно являются функциями (например, [x] — целая часть), добавляем к выходной строке символ этой функции.

•Если символ является бинарной операцией о1, тогда:

1) пока на вершине стека префиксная функция…

…ИЛИ операция на вершине стека приоритетнее o1

…ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1

…выталкиваем верхний элемент стека в выходную строку;

10