(Първо публикувано на 30.01.2017)
Днес ще ви покажа един прост алгоритъм за намиране на символен низ (последователност от символи) в друг символен низ.
Сигурно ви е минавало през ума, че има някаква магия, която се случва когато използвате методи като contains() или indexOf() в Java при работа със String обекти (примерно).
Нека да видим как става! 😀
ОПИСАНИЕ:
Този алгоритъм спада към “brute force” категорията, защото при него последователно преглеждаме всеки един символ от символен низ, докато не намерим съвпадение с търсения от нас “подниз” (substring).
С този алгоритъм ще намерим индекса на първия символ от подниза в низа (индексът ще е -1, ако поднизът не се среща никъде).
Това се счита за “наивен похдод”, тъй като е най-неефективният алгоритъм за намиране на подниз в низ (но пък за сметка на това е прост).
АЛГОРИТЪМ:
Имаме 2 символни низа:
- текст — от n символа
- шаблон — от m символа (*)
Използваме помощна променлива startIndex, която помни от кой индекс в текста ще започнем да търсим подниза. В началото startIndex = 0.
Ако startIndex <= (n — m), сравняваме по двойки първите m символа от текста (започващи от индекс startIndex нататък) с m-те символа на шаблона. Иначе приключваме алгоритъма (поднизът не е намерен) (**).
Ако всяка двойка се състои от два еднакви символа, приключваме алгоритъма (резултатът е равен на startIndex). Иначе увеличаваме startIndex с 1 и повтаряме стъпка 2.
(*) Дължината на шаблона не може да надвишава дължината на текста
(**) След тази начална позиция няма достатъчно символи за сравнение на целия шаблон.
ПРИМЕР:
Нека имаме следния символен низ (текст):
NOAH NOTICED
И искаме да октрием следния подниз (шаблон) в него:
NOT
Откъде да започнем? Нека първо представим символния низ като масив от символи (игнорираме знака ‘\0’):
Виждаме, че дължината на текста е 12 символа, следователно n = 12.
Шаблонът има дължина 3 символа, следователно m = 3.
Лесно пресмятаме, че максималният начален индекс ще е 9, защото m-n = 9. Това ще е най-лошият случай, при който поднизът започва от индекс 9 и свършва в индекс 11. От 10 няма как да започне, тъй като дължината му е 3 символа.
В началото казваме, че startIndex = 0, следователно ще сравним първите m на брой символа от текста с тези от шаблона, т.е. елементите с индекс от 0 до 2 включително:
При първите 2 символа имаме съвпадение, но последният символ e различен. 😔 Следва да увеличим стойността на startIndex с 1 (т.е. startIndex = 1) и да повторим същата процедура:
Този път нямаме съвпадение още от първия символ, затова няма смисъл да проверяваме следващите два. Просто увеличваме startIndex с 1 (startIndex = 2) и повтаряме процедурата докато не стигнем до индекс 5:
startIndex += 1 (startIndex = 3):
startIndex += 1 (startIndex = 4):
startIndex += 1 (startIndex = 5):
Тук вече имаме цялостно съвпадение!
Интересува ни текущата стойност на startIndex, която е 5.
Това означава, че поднизът се среща в низа от индекс 5 до 7 включително. 😉
ИМПЛЕМЕНТАЦИЯ (Java):
—
Това е за днес! Ако видите някоя неточност — tell meee. 😅
Top comments (0)