Алгоритм Апостолико-Крочемора - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:15:37Z

rollbackEdits.php mass rollback

185.220.102.8 в 05:51, 1 сентября 2022

2022-09-01T05:51:11Z

146.120.76.217: Подправлен алгоритм

2020-04-27T12:24:19Z

Подправлен алгоритм

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

2016-03-17T19:05:25Z

‎Пример

Voidmaster: /* Описание алгоритма */

2016-03-17T18:26:26Z

‎Описание алгоритма

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

2016-03-17T18:11:41Z

‎Псевдокод

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

2016-03-16T20:05:08Z

‎Псевдокод

Voidmaster: /* Описание алгоритма */

2016-03-16T19:10:06Z

‎Описание алгоритма

Voidmaster в 18:33, 16 марта 2016

2016-03-16T18:33:27Z

Voidmaster: /* Описание алгоритма */

2016-03-16T18:27:40Z

‎Описание алгоритма

← Предыдущая		Версия 16:15, 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 Майкл Наки].
−	\|}
−
	'''Алгоритм Апостолико — Крочемора''' (англ. ''Apostolico — Crochemore algorithm'') — алгоритм [[Поиск подстроки в строке\|поиска подстроки в строке]].		'''Алгоритм Апостолико — Крочемора''' (англ. ''Apostolico — Crochemore algorithm'') — алгоритм [[Поиск подстроки в строке\|поиска подстроки в строке]].

← Предыдущая		Версия 05:51, 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 Майкл Наки].
		+	\|}
		+
	'''Алгоритм Апостолико — Крочемора''' (англ. ''Apostolico — Crochemore algorithm'') — алгоритм [[Поиск подстроки в строке\|поиска подстроки в строке]].		'''Алгоритм Апостолико — Крочемора''' (англ. ''Apostolico — Crochemore algorithm'') — алгоритм [[Поиск подстроки в строке\|поиска подстроки в строке]].

@@ Строка 58: / Строка 58: @@
         i++
         j++
-        '''if''' x[i] == x[j]
+        '''if''' i < m '''and''' x[i] == x[j]
            t[i] = t[j]
         '''else'''
@@ Строка 65: / Строка 65: @@
   '''vector''' aG('''string''' x, '''string''' y): <font color=green>//<tex>x</tex> {{---}} образец, <tex>y</tex> {{---}} текст</font>
      '''int''' l
-     '''int''' t[x.size]
+     '''int''' t[x.size + 1]
      '''vector''' v
@@ Строка 90: / Строка 90: @@
         '''if''' i == l
            k = max(0, k - 1) <font color=green>// если <tex>i = l</tex> и <tex>x[i] \neq y[i + j]</tex>, тогда следующая тройка <tex>(l, j + 1, \max(0, k - 1))</tex></font>
-        '''else'''
+        '''else if''' t[i] <tex>\leqslant</tex> l      <font color=green>// если <tex>t[i] \leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex></font>
-          '''if''' t[i] <tex>\leqslant</tex> l      <font color=green>// если <tex>t[i] \leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex></font>
+          k = max(0, t[i])
-             k = max(0, t[i])
+          i = l
-             i = l
+       '''else'''              <font color=green>// если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</tex></font>
-          '''else'''              <font color=green>// если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</tex></font>
+          k = l
-             k = l
+          i = t[i]
      '''return''' v

@@ Строка 105: / Строка 105: @@
 |[[Файл:Apostolico-Crochemore-step-1.png|500px]]
 |<tex>(1, 0, 0)</tex>
-|step 1
+|Подставив шаблон к позиции <tex>0</tex> получим, что <tex>x[1] \neq y[1]</tex>. Вычислив сдвиг, получим <tex>j = 1</tex>.
 |-align="center"
 |[[Файл:Apostolico-Crochemore-step-2.png|500px]]
 |<tex>(1, 1, 0)</tex>
-|step 2
+|Подставив шаблон к позиции <tex>1</tex> получим, что <tex>x[0, \ldots , 3] = y[1, \ldots , 4]</tex>. Следовательно, <tex>x</tex> подстрока <tex>y</tex> в позиции <tex>1</tex>. Вычислив сдвиг, получим <tex>j = 4</tex>.
 |-align="center"
 |[[Файл:Apostolico-Crochemore-step-3.png|500px]]
 |<tex>(1, 4, 1)</tex>
-|step 3
+|Подставив шаблон к позиции <tex>4</tex> получим, что <tex>x[1] \neq y[5]</tex>. Вычислив сдвиг, получим <tex>j = 5</tex>.
 |-align="center"
 |[[Файл:Apostolico-Crochemore-step-4.png|500px]]
 |<tex>(1, 5, 0)</tex>
-|step 4
+|Подставив шаблон к позиции <tex>5</tex> получим, что <tex>x[1] \neq y[6]</tex>. Вычислив сдвиг, получим <tex>j = 6</tex>.
 |-align="center"
 |[[Файл:Apostolico-Crochemore-step-5.png|500px]]
 |<tex>(1, 6, 0)</tex>
-|step 5
+|Подставив шаблон к позиции <tex>6</tex> получим, что <tex>x[1] \neq y[7]</tex>. Вычислив сдвиг, получим <tex>j = 7</tex>.
 |-align="center"
 |[[Файл:Apostolico-Crochemore-step-6.png|500px]]
 |<tex>(1, 7, 0)</tex>
-|step 6
+|Подставив шаблон к позиции <tex>7</tex> получим, что <tex>x[1] \neq y[8]</tex>. Вычислив сдвиг, получим <tex>j = 8</tex>.
 |-align="center"
 |[[Файл:Apostolico-Crochemore-step-7.png|500px]]
 |<tex>(1, 8, 0)</tex>
-|step 7
+|Подставив шаблон к позиции <tex>8</tex> получим, что <tex>x[0, \ldots , 3] = y[8, \ldots , 11]</tex>. Следовательно, <tex>x</tex> подстрока <tex>y</tex> в позиции <tex>8</tex>.
 |-
 |}

← Предыдущая		Версия 18:26, 17 марта 2016
Строка 21:		Строка 21:


−	Пусть теперь <tex>l = 0</tex>, если <tex>x = c ^ m</tex> и <tex>c \in \Sigma</tex>, иначе <tex>l</tex> равно позиции первого элемента, который не равен <tex>x[0]</tex> (<tex>x = a ^ l bu</tex>, где <tex>a \in \Sigma</tex>, <tex>b \in \Sigma</tex>, <tex>a \neq b</tex>, <tex>u \in \Sigma^*</tex>). На каждой ~~итерации алгоритма~~ мы ~~выполняем~~ сравнения ~~с шаблоном в следующем порядке~~: <tex>l, l + 1, \ldots , m - 2, m - 1, 0, 1, \ldots , l - 1</tex>.	+	Пусть теперь <tex>l = 0</tex>, если <tex>x = c ^ m</tex> и <tex>c \in \Sigma</tex>, иначе <tex>l</tex> равно позиции первого элемента, который не равен <tex>x[0]</tex> (<tex>x = a ^ l bu</tex>, где <tex>a \in \Sigma</tex>, <tex>b \in \Sigma</tex>, <tex>a \neq b</tex>, <tex>u \in \Sigma^*</tex>). При каждой подстановке шаблона к тексту к позиции <tex>i</tex> мы проводим следующие сравнения: <tex>x[l] = y[i + l], x[l + 1] = y[i + l + 1], \ldots , x[m - 2] = y[i + m - 2], x[m - 1] = y[i + m - 1],</tex><tex> x[0] = y[i], x[1] = y [i + 1], \ldots , x[l - 1] = y[i + l - 1]</tex>.
		+

	Во время поиска вхождений мы рассматриваем данную тройку <tex>(i, j, k)</tex> где:		Во время поиска вхождений мы рассматриваем данную тройку <tex>(i, j, k)</tex> где:

@@ Строка 80: / Строка 80: @@
      '''while''' j <tex>\leqslant</tex> y.size - x.size
         '''while''' i < x.size '''and''' x[i] == y[i + j]  <font color=green>// если <tex>x[i] = y[i + j]</tex></font>
-           ++i                                <font color=green>// тогда следующая тройка <tex>(i + 1, j, k)</tex></font>
+           ++i                                 <font color=green>// тогда следующая тройка <tex>(i + 1, j, k)</tex></font>
         '''if''' i <tex>\geqslant</tex> x.size
-           '''while''' k < l '''and''' x[k] == y[j + k]
+           '''while''' k < l '''and''' x[k] == y[j + k] <font color=green>// если <tex>k < l</tex> и <tex>x[k] = y[j + k]</tex></font>
-              ++k
+              ++k                           <font color=green>// тогда следующая тройка <tex>(i, j, k + 1)</tex></font>
-           '''if''' k <tex>\geqslant</tex> l
+           '''if''' k <tex>\geqslant</tex> l           <font color=green>// если <tex>k = l</tex></font>
-              v.pushBack(j) <font color=green>// найдена подстрока в позиции j</font>
+              v.pushBack(j)   <font color=green>// тогда найдена подстрока в позиции j</font>
-        j += i - t[i] <font color=green>// вычисляем новый сдвиг</font>
+        j += i - t[i]         <font color=green>// вычисляем новый сдвиг</font>
         '''if''' i == l
-           k = max(0, k - 1) <font color=green>// если <tex>i = j</tex> и <tex>x[i] \neq y[i + j]</tex>, тогда следующая тройка <tex>(l, j + 1, \max(0, k - 1))</tex></font>
+           k = max(0, k - 1) <font color=green>// если <tex>i = l</tex> и <tex>x[i] \neq y[i + j]</tex>, тогда следующая тройка <tex>(l, j + 1, \max(0, k - 1))</tex></font>
         '''else'''
-           '''if''' t[i] <tex>\leqslant</tex> l  <font color=green>// если <tex>t[i] \leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex></font>
+           '''if''' t[i] <tex>\leqslant</tex> l      <font color=green>// если <tex>t[i] \leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex></font>
               k = max(0, t[i])
               i = l
-           '''else'''   <font color=green>// если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</tex></font>
+           '''else'''              <font color=green>// если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</tex></font>
               k = l
               i = t[i]

@@ Строка 27: / Строка 27: @@
 * <tex>0 \leqslant k \leqslant l</tex> и <tex>x[0, \ldots, k - 1] = y[j, \ldots , j + k - 1]</tex>
 * <tex>l \leqslant i < m</tex> и <tex>x[l, \ldots, i - 1] = y[j + l, \ldots , i + j - 1]</tex>
 Вначале инициализируем эту тройку <tex>(l, 0, 0)</tex>.
 Теперь опишем, как по уже вычисленной тройке <tex>(i, j, k)</tex> перейти к следующей.

← Предыдущая		Версия 18:33, 16 марта 2016
Строка 21:		Строка 21:


−	Пусть теперь <tex>l = 0</tex>, если <tex>x = c ^ m</tex> и <tex>c \in \Sigma</tex>, иначе <tex>l</tex> равно позиции первого элемента, который не равен <tex>x[0]</tex> (<tex>x = a ^ l bu</tex>, где <tex>a</tex> и <tex>b \in \Sigma</tex>, а <tex>u \in \Sigma^*</tex> и <tex>a \~~neq b~~</tex>). На каждой итерации алгоритма мы выполняем сравнения с шаблоном в следующем порядке: <tex>l, l + 1, \ldots , m - 2, m - 1, 0, 1, \ldots , l - 1</tex>.	+	Пусть теперь <tex>l = 0</tex>, если <tex>x = c ^ m</tex> и <tex>c \in \Sigma</tex>, иначе <tex>l</tex> равно позиции первого элемента, который не равен <tex>x[0]</tex> (<tex>x = a ^ l bu</tex>, где <tex>a \in \Sigma</tex>, <tex>b \in \Sigma</tex>, <tex>a \neq b</tex>, <tex>u \in \Sigma^*</tex>). На каждой итерации алгоритма мы выполняем сравнения с шаблоном в следующем порядке: <tex>l, l + 1, \ldots , m - 2, m - 1, 0, 1, \ldots , l - 1</tex>.

	Во время поиска вхождений мы рассматриваем данную тройку <tex>(i, j, k)</tex> где:		Во время поиска вхождений мы рассматриваем данную тройку <tex>(i, j, k)</tex> где:

← Предыдущая		Версия 18:27, 16 марта 2016
Строка 17:		Строка 17:

	[[Файл:Apostolico-Crochemore-Shifts.png]]		[[Файл:Apostolico-Crochemore-Shifts.png]]
−	<tex>v</tex> {{---}} помеченный бордер строки <tex>u</tex>.	+
		+	Примечание: <tex>v</tex> {{---}} помеченный бордер строки <tex>u</tex>.