Пошук підрядка в рядку с, purecodecpp
Сам алгоритм в принципі дуже простий. Є два рядки. Наприклад "Hello world" і "lo"
Працювати будемо в два цикли:
- Перший буде виконувати прохід по всій рядку, і шукати місце розташування першої літери шуканого рядка ( "lo").
- Другий, починаючи з знайденої позиції першої літери - звіряти, які букви стоять після неї і скільки з них підряд збігаються.
Проілюструємо пошук підрядка в рядку:
На перших двох ітераціях циклу порівнювані літери не будуть збігатися (виділено червоним). На третій ітерації шукана буква (перший символ шуканого слова) збіглася з символом у рядку, де відбувається пошук. При такому збігу в роботу включається другий цикл. Він покликаний відраховувати кількість символів після першого в шуканої рядку, які будуть співпадати з символами в рядку вихідної. Якщо один з наступних символів не збігається - цикл завершує свою роботу. Немає сенсу ганяти цикл даремно, після першого розбіжності, так як вже зрозуміло, що шуканого тут немає.
На третій ітерації збігся тільки перший символ шуканої рядка, а ось другий вже не збігається. Доведеться першого циклу продовжити роботу. Четверта ітерація дає необхідні результати - збігаються всі символи шуканої рядка з частиною вихідної рядки. А раз все символи збіглися - підрядок знайдена. Роботу алгоритму можна закінчити.
Подивимося, як виглядає класичний код пошуку підрядка в рядку в С ++:
Пошук підрядка в рядку
Два циклу виконують кожен свою задачу. Один тупотить по рядку в надії знайти «голову» шуканого слова (перший символ). Другий з'ясовує, чи є після знайденої «голови» «тіло» шуканого. Причому перевіряє, чи не лежить це «тіло» в кінці рядка. Тобто чи не є довжина знайденого слова на одиницю більше довжини шуканої рядка, якщо враховувати, що в цю одиницю потрапляє Нулла-термінатор ( '\ 0').
Ми бачимо, що програма знайшла початок підрядка pa в осередках символьного масиву з індексом 0 і 4. Але чому? Адже в слові parapapa 3 таких підрядка. Вся справа в '\ 0'.
Детально про це
Справа в тому, що символи Сі-рядків зберігаються в символьному масиві. Кожен рядок характеризується так званим ASCIIZ властивістю. Ця абревіатура буквально перекладається як «рядок, яка закінчується символом з кодом рівним нулю» - аски-зеро.
Тонкощі полягають в тому, що якщо шукане знаходиться в самому кінці рядка, доведеться враховувати і це зеро. Воно теж є частиною рядка, і при такому алгоритмі ще й збігається з кінцем шуканого рядка.
Наприклад рядки: "Remember Harry number room" і "room" насправді виглядають як "Remember Harry number room \ 0" і "room \ 0". Де '\ 0'. символ з кодом 0, який говорить, що рядок закінчилася. До речі саме такий підхід і дозволяє писати такі цикли як:
Якщо ми хочемо знайти слово room. стоїть в середині слова, нам потрібно порівнювати тільки 4 символу, але якщо раптом шукане зустрінеться лише в кінці - нам потрібно вже порівнювати не 4 символу, а ... 5. Чи перевіряти, чи не варто після нуль-термінатор цей. В цьому немає нічого складного. До такої рядку потрібно просто звикнути.
В цілому зміст самого алгоритму на цьому закінчується. Більше ніяких складнощів крім нуля в кінці рядка немає. Однак, слід звернути увагу на множинність пошуку. Що, якщо нам необхідно знайти в рядку кілька позицій? Скільки разів шукане слово зустрічається в рядку і в яких місцях? Саме це і покликаний контролювати третій параметр - int n - номер входження в рядок. Якщо поставити туди одиницю - він знайде перший збіг шуканого. Якщо двійку, він змусить перший цикл пропустити знайдене перше, і шукати друге. Якщо трійку - шукати третє і так далі. З кожним знайденим шуканим словом, цей лічильник входжень зменшується на одиницю. Це і дозволяє описати пошук в циклі: