Алгоритм текстового поиска является основным методом обработки текста и поиска информации. Этот алгоритм позволяет нам находить и идентифицировать вхождения подстроки(или шаблона) в большом фрагменте текста.
Как это работает
- Начните с более крупного фрагмента текста(или документа) и подстроки для поиска.
- Итерация через каждый символ текста последовательно.
- Сравните подстроку с частью текста той же длины, что и подстрока. Если совпадение найдено, запишите текущую позицию.
- Перейдите к следующей позиции и продолжите сравнение.
Пример
Рассмотрим текст: «Давайте найдем подстроку в этом тексте, чтобы увидеть, как работает алгоритм».
И подстрока для поиска: "substring"
- Начните с позиции 0. Сравните
Let'
с «подстрокой». Не совпадает. - Перейти на позицию 1. Сравните
et's
с "substring". Не совпадает. - Перейти на позицию 2. Сравнить
t's
" с "substring". Нет совпадений. - Перейти на позицию 3. Сравните
's s
с "substring". Не совпадает. - Перейти на позицию 4. Сравните
se
с "substring". Не совпадает. - Перейти на позицию 5. Сравните
sea
с "substring". Не совпадает. - Переместитесь на позицию 6. Сравните
earc
с "substring". Не совпадает. - Перейти на позицию 7. Сравните
arch
с "substring". Не совпадает. - Перейти к позиции 8. Сравнить
rch
" с "substring". Нет совпадения. - Перейти на позицию 9. Сравните
ch w
с "substring". Не совпадает. - Переместитесь на позицию 10. Сравните
h wi
с "substring". Не совпадает. - Перейти на позицию 11. Сравнить "
wit
с "substring". Нет совпадения. - Переместитесь на позицию 12. Сравните
with
с «подстрокой». Не совпадает. - Переместитесь на позицию 13. Сравните
ithi
с "substring". Не совпадает. - Переместитесь на позицию 14. Сравните
thin
с "substring". Не совпадает. - Переместитесь на позицию 15. Сравните
hinn
с "substring". Не совпадает. - Переместитесь на позицию 16. Сравните
in t
с "substring". Не совпадает. - Переместитесь на позицию 17. Сравните
n th
с "substring". Не совпадает. - Перейти на позицию 18. Сравнить "
thi
с "substring". Нет совпадений. - Переместитесь на позицию 19. Сравните
this
с "substring". Не совпадает. - Перейти на позицию 20. Сравнить
his
" с "substring". Нет совпадений. - Переместитесь на позицию 21. Сравните
is t
с "substring". Не совпадает. - Переместитесь на позицию 22. Сравните
s te
с "substring". Не совпадает. - Переместитесь на позицию 23. Сравните
ubst
с "substring". Не совпадает. - Переместитесь на позицию 24. Сравните
bstr
с "substring". Не совпадает. - Переместитесь на позицию 25. Сравните
stre
с "substring". Не совпадает. - Переместитесь на позицию 26. Сравните
trin
с "substring". Не совпадает. - Переместитесь на позицию 27. Сравните
ring
с "substring". Совпадение найдено, рекордная позиция 27.
Подстрока "substring" находится на позиции 27 в тексте.
Пример кода на С++
В этом примере textSearch
функция используется для поиска позиций подстроки «substring» в тексте. Результатом будет вектор, содержащий начальные позиции совпадений.