Поиск подстроки
Поиск подстроки — это проверка, содержится ли заданный фрагмент в строке, и определение позиции, с которой он начинается. Например, в строке «информатика» подстрока «форма» начинается с третьего символа, если считать позиции с единицы.
Как определяется позиция
При последовательном поиске сравнивают искомый фрагмент с участками исходной строки одинаковой длины. Если все символы совпали, найдено вхождение. Обычно позицию считают либо с единицы, либо с нуля — это зависит от языка программирования и принятой в задаче нумерации.
Здесь \(s\) — исходная строка, \(p\) — искомая подстрока, \(m\) — её длина, а \(i\) — индекс начала совпадения. Формула означает, что подряд идущие символы строки \(s\), начиная с \(i\), равны символам \(p\).
В строке «абракадабра» ищем «кад». Совпадение начинается с символа «к». При нумерации с единицы позиция равна 5, а при нумерации с нуля индекс равен 4. Если ищем только первое совпадение, достаточно остановиться после его обнаружения.
Поиск подстроки отвечает на вопрос о последовательных символах. Проверка наличия отдельных символов в любом порядке — другая задача. Также позиция первого вхождения и число всех вхождений не всегда совпадают с результатом поиска: для первого результата используется поиск первого вхождения.
Какова позиция начала подстроки «дом» в строке «водомёт», если считать позиции с нуля?
Главное
- Подстрока должна состоять из соседних символов исходной строки.
- Поиск подстроки определяет факт вхождения и, при необходимости, позицию начала.
- Всегда уточняйте, начинается ли нумерация позиций с нуля или с единицы.