Работа со строками

Строку можно определить и как последовательность символов произвольной длины, и как массив символов, так как к каждому символу строки допустимо обращение по его индексу.

Отношение порядка на множестве строк может быть определено следующим образом. Пусть даны две строки X и Y длины т.

Символ V читается как «для любого», символ 3 - «существует».

Следовательно, сравнение строк сводится к поиску их несовпадающих частей. Если неравных частей не существует, можно говорить о равенстве строк.

Алгоритм сравнении строк

Пусть заданы две строки X и Y. Необходимо определить, равны ли эти строки между собой.

• 1. i= 1.
• 2. Пока (Xi = Yi) и (i < ш) выполнять i = i + 1.
• 3. Если i > ш, то X = Y.
• 4. Иначе, если Xi < Yi, то X
• 5. Иначе X>Y.

где т - максимальная из длин строк X и Y.

Поиск строки в массиве строк

Пусть задан упорядоченный массив Т из п строк. Необходимо найти элемент массива, равный заданной строке X. Так как массив упорядочен, для поиска в массиве используем алгоритм оптимального бинарного поиска, а для сравнения строк - приведенный выше алгоритм.

• 1. L = 1. Левая граница массива.
• 2. R = п. Правая граница массива.
• 3. Если R < L, то перейти на шаг 9.
• 4. s = |_(L + R)/2_|.
• 5. i = 1.
• 6. Пока (Т₈д = Xi) и (i < m) выполнять i = i + 1.
• 7. Если (T_s,i < Х;) и (i < m), to L = s + 1. Перейти на шаг 3.
• 8. Иначе (T_s>i> ХО R = s. Перейти на шаг 3.
• 9. i= 1.

Ю.Пока (TR,i= Xi) и (i < m) выполнять i = i + 1.

11.Если i>m, то поиск удачен, в противном случае - строки нет в массиве, где m - максимальная из длин сравниваемых строк.

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

Пусть задана строка 5 из п элементов и строка Р из m элементов, причем О <т<п. Необходимо обнаружить первое вхождение подстроки Р в строку S.

• 1. i = -1.
• 2. i = i + 1. { указатель индекса, с которого осуществляется поиск }
• 3. j = 1. { счетчик по подстроке Р }
• 4. Пока (j < m) и (Si+j = Pj) выполнять j = j + 1.

• 5. Если (j < m) и (i < n - m) - перейти на шаг 2.
• 6. Если j > m, поиск удачен. Подстрока Р входит в строку S с позиции i + 1.

Иначе - поиск неудачен.