Лексикографическое сравнение строк

Лексикографическое сравнение строк — это сравнение слов так, как они располагаются в словаре: сначала сравниваются первые символы, затем вторые и так далее. Тема нужна для определения порядка слов, поиска минимальной или максимальной строки и решения задач, где строки требуется отсортировать.

Что такое лексикографический порядок

Перед изучением темы полезно повторить, что строка состоит из символов, а каждый символ имеет индекс. В большинстве учебных задач нумерация индексов начинается с нуля: первый символ имеет индекс 0. Подробнее о строении строки рассказано на страницах символ строки и индекс символа.

Пусть есть две строки \(A\) и \(B\). Алгоритм сравнения таков: сначала сравниваются \(A[0]\) и \(B[0]\). Если они различаются, результат определяется только ими. Если равны, сравниваются символы с индексом 1, затем 2 и так далее. Сравнение заканчивается при первом различии или после окончания одной из строк.

Например, строка «кот» меньше строки «кит», потому что первые символы равны, а на индексе 1 сравниваются «о» и «и». В русском алфавите «и» расположена раньше «о», поэтому «кит» меньше «кот».

Сравнение символов и строк разной длины

Чтобы сравнивать символы, нужно знать их порядок. В задачах с русскими или английскими буквами обычно используется порядок алфавита. Для цифр порядок естественный: «0» меньше «1», «1» меньше «2» и так далее. В программировании фактический порядок определяется кодами символов, поэтому прописные и строчные буквы могут располагаться не так, как ожидается по словарю.

Особый случай возникает, когда все символы короткой строки совпали с началом длинной. Тогда короткая строка считается меньшей. Например, «кот» меньше «коты», потому что после совпадения «к», «о», «т» первая строка закончилась.

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

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

При программном сравнении удобно идти по индексам от 0 до длины меньшей строки минус один. На каждой позиции проверяются символы. Как только найдено различие, можно сразу вернуть результат. Если различий нет, сравниваются длины строк: меньшая длина означает меньшую строку.

1def compare_strings(a, b):
2    m = min(len(a), len(b))
3    for i in range(m):
4        if a[i] < b[i]:
5            return -1
6        if a[i] > b[i]:
7            return 1
8    if len(a) < len(b):
9        return -1
10    if len(a) > len(b):
11        return 1
12    return 0

Значения результата обычно трактуют так: \(-1\) означает \(A<B\), \(0\) — равенство, \(1\) — \(A>B\). В конкретном языке программирования сравнение строк может быть встроено, но для экзамена важно понимать, какой алгоритм скрывается за операцией сравнения.

Разбор задачи на порядок слов

Рассмотрим набор строк: «мел», «мель», «мак», «море», «мама». Требуется расположить их по возрастанию. Сначала сравним первые символы. Все слова начинаются с «м», поэтому переходим к следующему символу. У слов «мел» и «мель» второй символ «е», у остальных — «а» или «о».

В последнем шаге важно не перепутать сравнение всей строки и сравнение длины. Например, «море» длиннее «мак», но порядок определился уже на третьем символе: «к» раньше «р». Длина учитывается только для строк, у которых совпала вся общая часть.

1words = ["мел", "мель", "мак", "море", "мама"]
2words.sort()
3print(words)

Сортировка и типичные экзаменационные задачи

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

• Для поиска минимума запомните первую строку, затем сравнивайте её с каждой следующей.
• Для проверки возрастания сравнивайте соседние строки: должно выполняться \(S[i]\le S[i+1]\).
• Для проверки строгого возрастания используйте условие \(S[i]<S[i+1]\).
• Если нужно отсортировать строки по убыванию, меняйте направление сравнения или просматривайте результат сортировки с конца.
• Если строки содержат числа, уточните условие: сравнение как строк и сравнение числовых значений дают разные результаты.

Если строка состоит из цифр и обозначает число, сначала нужно преобразовать её в число или выполнить разбор чисел в строке. Если же условие прямо говорит «слова», «строки» или «символы», используйте лексикографическое сравнение.