8.1. Поиск в строке

Определения и обозначения

Строка — последовательность символов, в которой можно искать заданную последовательность. Например, строкой может быть слово, предложение или текстовый фрагмент. Она служит областью поиска: именно в ней проверяют, есть ли нужный образец. Без указания строки нельзя определить, где искать совпадение.

Подстрока — последовательность символов, входящая в состав другой строки; она может состоять как из одного, так и из нескольких символов. Например, «а» — подстрока слова «мама», а «мам» — подстрока той же строки. Подстрока задаёт точный образец для сравнения. Поэтому важно учитывать порядок символов, а не только их наличие.

Поиск в строке — определение того, встречается ли заданная подстрока в строке и где находится её вхождение. Поиск нужен, чтобы находить фрагменты текста, проверять введённые данные или искать слово в большом тексте. В качестве образца может выступать как один символ, так и целое слово. Результат отвечает на вопрос о наличии совпадения и, если оно есть, о его расположении.

Позиция вхождения — место, с которого начинается найденная подстрока. Например, если слово начинается с третьего символа, его позиция в привычном отсчёте равна 3. Однако в программе номер зависит от языка: в одних языках первый символ имеет индекс 0, в других его позиция равна 1. Перед использованием результата нужно выяснить, какое правило применяет язык или функция поиска.

Как это устроено

Сначала определяют строку для поиска и образец — подстроку, которую требуется обнаружить. Это разделяет две роли: строка содержит материал для проверки, а образец задаёт, что именно считается совпадением. Если перепутать их, алгоритм будет искать не тот фрагмент или в неподходящем тексте. Образец следует записать точно, включая порядок символов и, если это важно, регистр букв.

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

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

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

Если проверены все возможные позиции, а полного совпадения нет, результат должен показывать отсутствие образца. Одной позиции в таком случае сообщать нельзя: она могла бы быть принята за настоящее вхождение. Функции разных языков обозначают отсутствие по-разному — например, специальным значением или отдельным признаком. Поэтому результат нужно проверять по правилам используемой функции, а не угадывать по числу.

Результаты поиска подстроки

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

Разбор задач

Задача 1. Найти, встречается ли символ «а» в заданной строке. Здесь образец состоит всего из одного символа, поэтому для совпадения достаточно проверить, равен ли ему символ строки на очередной позиции. Не нужно искать целое слово или требовать, чтобы «а» стояла отдельно от других букв. Если задача спрашивает только о наличии, достаточно первого совпадения.

1. Запишем заданную строку и образец «а».
2. Проверим символы строки по очереди, сравнивая каждый с образцом.
3. При первом равенстве отметим, что символ найден, и прекратим поиск; если строка закончилась, совпадения нет.

Ответ: сообщить, встречается ли «а»; если требуется только факт наличия, позицию можно не выводить. Если нужна позиция, её следует взять из результата поиска и истолковать с учётом нумерации языка.

Задача 2. Найти позицию первого вхождения слова «код» в предложении. В отличие от поиска одного символа, здесь необходимо сравнивать сразу три символа подряд. Сначала проверяют начало предложения, затем следующий возможный участок и так далее. Как только все буквы слова совпали в правильном порядке, более поздние позиции уже не нужны.

1. Примем предложение за строку, а слово «код» — за образец.
2. Последовательно проверим участки длиной три символа, начиная с каждой возможной позиции.
3. При первом полном совпадении запишем позицию начала слова и остановимся.
4. Если все участки проверены без совпадения, используем результат, который обозначает отсутствие слова.

Ответ: вывести позицию первого совпадения либо сообщить, что слова в предложении нет. Перед выводом позиции проверьте, начинается ли отсчёт с 0 или с 1. Если поиск выполняется по предложению, совпадение внутри другого слова тоже может считаться вхождением, если условие отдельно не требует искать только отдельное слово.

Задача 3. Найти все позиции вхождения заданной подстроки, в том числе при повторениях. В этой задаче остановка после первого совпадения приведёт к неполному ответу. После обнаружения образца нужно перейти к проверке следующих возможных начал. Если совпадения могут перекрываться, нельзя перескакивать сразу за весь найденный фрагмент.

1. Зададим строку и образец, затем начнём последовательную проверку с первой возможной позиции.
2. При полном совпадении запишем его начальную позицию.
3. Чтобы не пропустить перекрывающееся вхождение, продолжим со следующей позиции после начала найденного совпадения.
4. Будем повторять проверку, пока не закончатся позиции, в которых помещается весь образец.

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

Типичные ошибки

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

Неверная трактовка результата функции может привести к тому, что отсутствие подстроки примут за позицию или наоборот. Это происходит из-за различий между языками и функциями: они могут возвращать номер, специальное значение или отдельный признак. Проверяйте документацию и правило нумерации позиций, а также отдельно обработайте случай отсутствия. Полезно проверить программу на строке, где образца точно нет.

Остановка после первого совпадения — ошибка, если нужно вывести все вхождения. Её допускают, когда не различают задачи «найти первое» и «найти все». Проверьте формулировку условия: слова «все позиции» требуют продолжить поиск после первого результата. В конце убедитесь, что алгоритм проверил все подходящие места.

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

Связь с другими темами

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

Поиск подстрок применяют при обработке текстов: например, чтобы найти слово или фрагмент предложения. Он помогает проверять введённые данные — выяснять, содержит ли значение нужный символ или последовательность. Тот же принцип используют при поиске фрагментов в файлах, где вместо короткой строки рассматривают более крупный текст. Умение различать первое и все вхождения делает такие проверки надёжнее.

Что запомнить

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