Алгоритм Бойера-Мура - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:21:39Z

rollbackEdits.php mass rollback

194.26.192.187 в 05:16, 1 сентября 2022

2022-09-01T05:16:24Z

94.45.102.149: /* Псевдокод */ неправильный код, пусть пересмотрят нормальные программисты, бред написан

2018-11-17T11:18:02Z

‎Псевдокод: неправильный код, пусть пересмотрят нормальные программисты, бред написан

I am dark black в 18:43, 20 января 2018

2018-01-20T18:43:50Z

Ateuhh: /* Псевдокод */

2016-05-19T06:50:31Z

‎Псевдокод

Ateuhh: /* Псевдокод */

2016-05-18T11:01:51Z

‎Псевдокод

Ateuhh: /* Пример */

2016-05-18T09:56:10Z

‎Пример

Ateuhh: /* Пример */

2016-05-18T09:48:52Z

‎Пример

Ateuhh: /* Псевдокод */

2016-05-18T09:40:11Z

‎Псевдокод

Ateuhh: /* Псевдокод */

2016-05-18T09:32:08Z

‎Псевдокод

← Предыдущая		Версия 16:21, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Алгоритм Бойера-Мура''', разработанный двумя учеными {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличие от многих других алгоритмов.		'''Алгоритм Бойера-Мура''', разработанный двумя учеными {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличие от многих других алгоритмов.

← Предыдущая		Версия 05:16, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Алгоритм Бойера-Мура''', разработанный двумя учеными {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличие от многих других алгоритмов.		'''Алгоритм Бойера-Мура''', разработанный двумя учеными {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличие от многих других алгоритмов.

@@ Строка 86: / Строка 86: @@
        '''return''' true
-Функция, возвращающая для позиции <tex>p</tex> длину максимальной подстроки, которая является суффиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.
+Функция, возвращающая для позиции <tex>p</tex> длину максимальной подстроки, которая является суффиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени. //здесь неправильно, нет смысла сравнивать элементы ШАБЛОНА С САМИМ СОБОЙ
     '''int''' suffixLength('''char'''[m] x, '''int''' p):
        '''int''' len = 0

← Предыдущая		Версия 18:43, 20 января 2018
Строка 1:		Строка 1:
−	'''Алгоритм Бойера-Мура''', разработанный двумя учеными {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в ~~отличии~~ от многих других алгоритмов.	+	'''Алгоритм Бойера-Мура''', разработанный двумя учеными {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличие от многих других алгоритмов.

	Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.		Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.

@@ Строка 116: / Строка 116: @@
        '''vector <int>''' answer <font color=green>// вектор, содержащий все вхождения подстроки в строку</font>
        '''if''' m == 0
-          answer.push_back(-1) <font color=green>// Искомая подстрока является пустой</font>
+          answer.pushBack(-1) <font color=green>// Искомая подстрока является пустой</font>
           '''return''' answer
@@ Строка 128: / Строка 128: @@
           '''while''' x[j] == y[i]
              '''if''' j == 0
-                answer.push_back(i) <font color=green>// Найдена подстрока в позиции i</font>
+                answer.pushBack(i) <font color=green>// Найдена подстрока в позиции i</font>
              --i
              --j
           i += max(bmGs[m - 1 - j], bmBc[y[i]])
        '''if''' (answer == <tex> \varnothing </tex>)
-          answer.push_back(-1) <font color=green>// Искомая подстрока не найдена</font>
+          answer.pushBack(-1) <font color=green>// Искомая подстрока не найдена</font>
        '''return''' answer

@@ Строка 113: / Строка 113: @@
 Основная функция алгоритма Бойера-Мура
-    '''function''' BM('''char'''[n] y, '''char'''[m] x): '''int'''
+    '''function''' BM('''char'''[n] y, '''char'''[m] x): '''vector <int>'''
        '''if''' m == 0
-          '''return''' -1 <font color=green>// Искомая подстрока является пустой</font>
+          answer.push_back(-1) <font color=green>// Искомая подстрока является пустой</font>
        <font color=green>// Предварительные вычисления</font>
@@ Строка 126: / Строка 128: @@
           '''while''' x[j] == y[i]
              '''if''' j == 0
-                '''return''' i <font color=green>// Найдена подстрока в позиции i</font>
+                answer.push_back(i) <font color=green>// Найдена подстрока в позиции i</font>
              --i
              --j
           i += max(bmGs[m - 1 - j], bmBc[y[i]])
 ==Пример==

@@ Строка 147: / Строка 147: @@
 |[[Файл:BMexample1.png|550px]]
 |<tex>(7, 1)</tex>
-|Сравниванием последние символы, они неравны, поэтому сдвигаемся на <tex> bmGs[y[j]]</tex>, где <tex>y[j]</tex> - это не совпавший символ. В данном случае <tex>y[j]=7</tex>, а <tex> bmGs[7]= 1</tex>.
+|Сравниванием последние символы, они неравны, поэтому сдвигаемся на <tex> bmGs[y[j]]</tex>, где <tex>y[j]</tex> {{---}} это не совпавший символ. В данном случае <tex>y[j]=7</tex>, а <tex> bmGs[7]= 1</tex>.
 |-align="center"
 |[[Файл:BMexample2.png|550px]]

@@ Строка 147: / Строка 147: @@
 |[[Файл:BMexample1.png|550px]]
 |<tex>(7, 1)</tex>
-|Сравниванием последние символы, они неравны, поэтому сдвигаемся.
+|Сравниванием последние символы, они неравны, поэтому сдвигаемся на <tex> bmGs[y[j]]</tex>, где <tex>y[j]</tex> - это не совпавший символ. В данном случае <tex>y[j]=7</tex>, а <tex> bmGs[7]= 1</tex>.
 |-align="center"
 |[[Файл:BMexample2.png|550px]]
 |<tex>(8, 4)</tex>
-|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся.
+|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 4</tex>.
 |-align="center"
 |[[Файл:BMexample3.png|550px]]
 |<tex>(12, 7)</tex>
-|Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся.
+|Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся на <tex> bmGs[0]= 7</tex>.
 |-align="center"
 |[[Файл:BMexample4.png|550px]]
 |<tex>(19, 4)</tex>
-|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся.
+|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 4</tex>.
 |-align="center"
 |[[Файл:BMexample5.png|550px]]

@@ Строка 115: / Строка 115: @@
     '''function''' BM('''char'''[n] y, '''char'''[m] x): '''int'''
        '''if''' m == 0
-          '''return'''
+          '''return''' -1 <font color=green>// Искомая подстрока является пустой</font>
        <font color=green>// Предварительные вычисления</font>
-       '''int''' bmBc[] = preBmBc(x)
+       '''int'''<tex>[</tex> <tex>|\Sigma|</tex> <tex>]</tex> bmBc = preBmBc(x)
-       '''int''' bmGs[] = preBmGs(x)
+       '''int'''[m] bmGs = preBmGs(x)
        <font color=green>// Поиск подстроки</font>