AlgorithmO #19 - Търсене на символни низове (наивен подход)

Днес ще ви покажа един прост алгоритъм за намиране на символен низ (последователност от символи) в друг символен низ.

Сигурно ви е минавало през ума, че има някаква магия, която се случва когато използвате методи като contains() или indexOf() в Java при работа със String обекти (примерно).

Нека да видим как става! 😀

---

ОПИСАНИЕ:

Този алгоритъм спада към "brute force" категорията, защото при него последователно преглеждаме всеки един символ от символен низ, докато не намерим съвпадение с търсения от нас "подниз" (substring).


С този алгоритъм ще намерим индекса на първия символ от подниза в низа (индексът ще е -1 ако поднизът не се среща никъде).

Това се счита за "наивен похдод", тъй като е най-неефективният алгоритъм за намиране на подниз в низ (но пък за сметка на това е прост).

АЛГОРИТЪМ:

Имаме 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

При първите 2 символа имаме съвпадение, но последният символ e различен. 😔 Следва да увеличим стойността на startIndex с 1 (т.е. startIndex = 1) и да повторим същата процедура:

Индекс	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 = 2) и повтаряме процедурата докато не стигнем до индекс 5:

Индекс	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

startIndex += 1 (startIndex = 4):

Индекс	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 = 5):

Индекс	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, която е 5.

Това означава, че поднизът се среща в низа от индекс 5 до 7 включително. 😉

ИМПЛЕМЕНТАЦИЯ (Java):

	public class StringSearch {
	public static int getSubstringStartIndex(String text, String pattern) {
	int n = text.length();
	int m = pattern.length();
	for (int startIndex = 0; startIndex <= ( n - m ); ++startIndex) {
	int i = 0;
	for (i = 0; i < m; ++i) {
	if (pattern.charAt(i) != text.charAt(startIndex + i)) {
	break;
	}
	}
	if (i == m) { // if all pairs of characters have matched
	return startIndex;
	}
	}
	return -1; // substring not found in string
	}
	public static void main(String[] args) {
	int substringStartIndex = getSubstringStartIndex("NOAH NOTICED", "NOT");
	System.out.println(substringStartIndex);
	}
	}

view raw ALGORITHMO-19-Naive-String-Search-Implementation.java hosted with ❤ by GitHub

---
Това е за днес! Ако видите някоя неточност - tell meee. 😅