Сигурно ви е минавало през ума, че има някаква магия, която се случва когато използвате методи като contains() или indexOf() в Java при работа със String обекти (примерно).
Нека да видим как става! 😀
---
ОПИСАНИЕ:
Този алгоритъм спада към "brute force" категорията, защото при него последователно преглеждаме всеки един символ от символен низ, докато не намерим съвпадение с търсения от нас "подниз" (substring).
С този алгоритъм ще намерим индекса на първия символ от подниза в низа (индексът ще е -1 ако поднизът не се среща никъде).
Това се счита за "наивен похдод", тъй като е най-неефективният алгоритъм за намиране на подниз в низ (но пък за сметка на това е прост).
Имаме 2 символни низа:
- текст - от n символа
- шаблон - от m символа *
1. Използваме помощна променлива startIndex, която помни от кой индекс в текста ще започнем да търсим подниза. В началото startIndex = 0.
* Дължината на шаблона не може да надвишава дължината на текста
** След тази начална позиция няма достатъчно символи за сравнение на целия шаблон.
И искаме да октрием следния подниз (шаблон) в него:
В началото казваме, че startIndex = 0, следователно ще сравним първите m на брой символа от текста с тези от шаблона, т.е. елементите с индекс от 0 до 2 включително:
При първите 2 символа имаме съвпадение, но последният символ e различен. 😔 Следва да увеличим стойността на startIndex с 1 (т.е. startIndex = 1) и да повторим същата процедура:
Този път нямаме съвпадение още от първия символ, затова няма смисъл да проверяваме следващите два. Просто увеличваме startIndex с 1 (startIndex = 2) и повтаряме процедурата докато не стигнем до индекс 5:
startIndex += 1 (startIndex = 4):
startIndex += 1 (startIndex = 5):
Тук вече имаме цялостно съвпадение!
Интересува ни текущата стойност на startIndex, която е 5.
АЛГОРИТЪМ:
Имаме 2 символни низа:
- текст - от n символа
- шаблон - от m символа *
1. Използваме помощна променлива startIndex, която помни от кой индекс в текста ще започнем да търсим подниза. В началото startIndex = 0.
2. Ако startIndex <= (n - m):
- сравняваме по двойки
първите m символа (започващи от индекс startIndex нататък) от текста
с m-те символа на шаблона.
Иначе приключваме алгоритъма (поднизът не е намерен) **.
3. Ако всяка двойка се състои от два еднакви символа:
- приключваме алгоритъма (резултатът е равен на startIndex)
Иначе увеличаваме startIndex с 1 и повтаряме стъпка 2.
** След тази начална позиция няма достатъчно символи за сравнение на целия шаблон.
ПРИМЕР:
Нека имаме следния символен низ (текст):
Нека имаме следния символен низ (текст):
NOAH NOTICED
И искаме да октрием следния подниз (шаблон) в него:
NOT
Откъде да започнем? Нека първо представим символния низ като масив от символи (игнорираме знака '\0'):
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
Стойност
|
N
|
O
|
A
|
H
|
N
|
O
|
T
|
I
|
C
|
E
|
D
|
Виждаме, че дължината на текста е 12 символа, следователно n = 12.
Шаблонът има дължина 3 символа, следователно m = 3.
Лесно пресмятаме, че максималният начален индекс ще е 9, защото m-n = 9. Това ще е най-лошият случай, при който поднизът започва от индекс 9 и свършва в индекс 11. От 10 няма как да започне, тъй като дължината му е 3 символа.
В началото казваме, че startIndex = 0, следователно ще сравним първите m на брой символа от текста с тези от шаблона, т.е. елементите с индекс от 0 до 2 включително:
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
Стойност
|
N
|
O
|
A
|
H
|
N
|
O
|
T
|
I
|
C
|
E
|
D
|
|
Шаблон
|
N
|
O
|
T
|
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
Стойност
|
N
|
O
|
A
|
H
|
N
|
O
|
T
|
I
|
C
|
E
|
D
|
|
Шаблон
|
N
|
O
|
T
|
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
Стойност
|
N
|
O
|
A
|
H
|
N
|
O
|
T
|
I
|
C
|
E
|
D
|
|
Шаблон
|
N
|
O
|
T
|
startIndex += 1 (startIndex = 3):
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
Стойност
|
N
|
O
|
A
|
H
|
N
|
O
|
T
|
I
|
C
|
E
|
D
|
|
Шаблон
|
N
|
O
|
T
|
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
Стойност
|
N
|
O
|
A
|
H
|
N
|
O
|
T
|
I
|
C
|
E
|
D
|
|
Шаблон
|
N
|
O
|
T
|
Индекс
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
Стойност
|
N
|
O
|
A
|
H
|
N
|
O
|
T
|
I
|
C
|
E
|
D
|
|
Шаблон
|
N
|
O
|
T
|
Това означава, че поднизът се среща в низа от индекс 5 до 7 включително. 😉
Няма коментари:
Публикуване на коментар