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

217.66.158.37: Перенаправление на Алгоритм Манакера

2016-04-18T20:00:37Z

Перенаправление на Алгоритм Манакера

94.25.229.141 в 21:15, 10 апреля 2016

2016-04-10T21:15:34Z

94.25.229.141 в 20:24, 10 апреля 2016

2016-04-10T20:24:32Z

188.162.65.15 в 21:41, 30 марта 2016

2016-03-30T21:41:14Z

188.162.65.15 в 21:00, 30 марта 2016

2016-03-30T21:00:43Z

188.162.64.2 в 12:50, 27 марта 2016

2016-03-27T12:50:29Z

188.162.64.2 в 10:33, 27 марта 2016

2016-03-27T10:33:39Z

188.162.64.2 в 10:25, 27 марта 2016

2016-03-27T10:25:14Z

188.162.65.6 в 16:41, 19 марта 2016

2016-03-19T16:41:34Z

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

2016-03-19T16:36:02Z

‎Псевдокод

← Предыдущая		Версия 20:00, 18 апреля 2016
Строка 1:		Строка 1:
−	~~{{Шаблон:Задача~~	+	#перенаправление [[Алгоритм Манакера]]
−	~~\|definition =~~
−	~~Пусть дана строка <tex>s</tex>, требуется посчитать количество~~ [[~~Основные_определения,_связанные_со_строками#palindrome \| палиндромов]] в ней.~~
−	}}
−
−	== Алгоритм ==
−	~~=== Идея ===~~
−	Рассмотрим сначала задачу поиска палиндромов нечетной длины. Центром строки нечетной длины назовем символ под индексом <tex>\left\lfloor \dfrac{\|t\|}{2}\right\rfloor</tex>. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск \| бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.
−
−	Для палиндромов четной длины алгоритм такой же. Центр строки четной длины {{---}} некий мнимый элемент между <tex>\dfrac{\|t\|}{2} - 1</tex> и <tex>\dfrac{\|t\|}{2}</tex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.
−
−	~~=== Псевдокод ===~~
−	~~'''int''' binarySearch(s : '''string''', center, shift : '''int'''):~~
−	~~''<font color=green>//shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1</font>''~~
−	~~'''int''' l = -1, r = min(center, s.length - center + shift), m = 0~~
−	~~'''while''' r - l != 1~~
−	~~m = l + (r - l) / 2~~
−	~~''<font color=green>//reversed_hash возвращает хэш развернутой строки s</font>''~~
−	~~'''if''' hash(s[center - m..center]) == reversed_hash(s[center + shift..center + shift + m])~~
−	~~l = m~~
−	~~'''else'''~~
−	~~r = m~~
−	~~'''return''' r~~
−
−	~~'''int''' palindromesCount(s : '''string'''):~~
−	~~'''int''' ans = 0~~
−	~~'''for''' i = 0 '''to''' s.length~~
−	~~ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)~~
−	~~'''return''' ans~~
−
−	~~=== Время работы ===~~
−	Изначальный подсчет хешей производится за <tex>O(\|s\|)</tex>. Каждая итерация будет выполняться за <tex>O(\log(\|s\|))</tex>, всего итераций {{---}} <tex>\|s\|</tex>. Итоговое время работы алгоритма <tex>O(\|s\|+\|s\|\cdot \log(\|s\|)) = O(\|s\|\cdot \log(\|s\|))</tex>.
−
−	~~=== Избавление от коллизий ===~~
−	У хешей есть один недостаток {{---}} коллизии: можно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив \| суффиксного массива]], но с дополнительной памятью <tex>O(\|s\|\cdot \log(\|s\|))</tex>. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..i + l]</tex> и <tex>s[j..j + l]</tex>. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной <tex>2^k</tex>, где <tex>k = \lfloor \log{l} \rfloor</tex>. Тогда наши строки совпадают, если <tex>c[k][i] = c[k][j]</tex> и <tex>c[k][i + l - 2^k] = c[k][j + l - 2^k]</tex>.
−
−	Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(\|s\|))</tex> на запрос, если предподсчитать все <tex>k</tex>, то <tex>O(1)</tex>.
−
−	~~==См. также==~~
−	*[[Суффиксный массив]]
−	*[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
−
−	~~==Источники информации==~~
−	* [http://e-maxx.ru/algo/suffix_array#5 MAXimal :: algo :: Суффиксный массив]
−	~~[[Категория:Алгоритмы и структуры данных]]~~
−	~~[[Категория:Суффиксный массив~~]]

@@ Строка 6: / Строка 6: @@
 == Алгоритм ==
 === Идея ===
-Рассмотрим сначала задачу поиска палиндромов нечетной длины. Центром строки нечетной длины назовем символ под индексом <tex>\lfloor \frac{|t|}{2}\rfloor</tex>. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.
+Рассмотрим сначала задачу поиска палиндромов нечетной длины. Центром строки нечетной длины назовем символ под индексом <tex>\left\lfloor \dfrac{|t|}{2}\right\rfloor</tex>. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.
-Для палиндромов четной длины алгоритм такой же. Центр строки четной длины {{---}} некий мнимый элемент между <tex>\frac{|t|}{2} - 1</tex> и <tex>\frac{|t|}{2}</tex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.
+Для палиндромов четной длины алгоритм такой же. Центр строки четной длины {{---}} некий мнимый элемент между <tex>\dfrac{|t|}{2} - 1</tex> и <tex>\dfrac{|t|}{2}</tex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.
 === Псевдокод ===

@@ Строка 6: / Строка 6: @@
 == Алгоритм ==
 === Идея ===
-Рассмотрим сначала задачу поиска палиндромов нечетной длины. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.
+Рассмотрим сначала задачу поиска палиндромов нечетной длины. Центром строки нечетной длины назовем символ под индексом <tex>\lfloor \frac{|t|}{2}\rfloor</tex>. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.
-Для палиндромов четной длины алгоритм такой же, только следует проверять вторую строку со сдвигом на единицу, при этом мы не посчитаем никакой палиндром дважды из-за четности-нечетности палиндромов.
+Для палиндромов четной длины алгоритм такой же. Центр строки четной длины {{---}} некий мнимый элемент между <tex>\frac{|t|}{2} - 1</tex> и <tex>\frac{|t|}{2}</tex>. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.
 === Псевдокод ===
@@ Строка 16: / Строка 16: @@
       '''while''' r - l != 1
           m = l + (r - l) / 2
-          '''if''' hash(s[center - m..center]) == hash(reverse(s[center + shift..center + shift + m]))
+         ''<font color=green>//reversed_hash возвращает хэш развернутой строки s</font>''
               l = m
           '''else'''
@@ Строка 32: / Строка 33: @@
 === Избавление от коллизий ===
-У хешей есть один недостаток {{---}} коллизии, возможно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]], но с дополнительной памятью <tex>O(|s|\cdot \log(|s|))</tex>. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..i + l]</tex> и <tex>s[j..j + l]</tex>. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной <tex>2^k</tex>, где <tex>k = \lfloor \log{l} \rfloor</tex>. Тогда наши строки совпадают, если <tex>c[k][i] = c[k][j]</tex> и <tex>c[k][i + l - 2^k] = c[k][j + l - 2^k]</tex>.
+У хешей есть один недостаток {{---}} коллизии: можно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]], но с дополнительной памятью <tex>O(|s|\cdot \log(|s|))</tex>. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..i + l]</tex> и <tex>s[j..j + l]</tex>. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной <tex>2^k</tex>, где <tex>k = \lfloor \log{l} \rfloor</tex>. Тогда наши строки совпадают, если <tex>c[k][i] = c[k][j]</tex> и <tex>c[k][i + l - 2^k] = c[k][j + l - 2^k]</tex>.
 Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(|s|))</tex> на запрос, если предподсчитать все <tex>k</tex>, то <tex>O(1)</tex>.

@@ Строка 32: / Строка 32: @@
 === Избавление от коллизий ===
-У хешей есть один недостаток {{---}} коллизии, возможно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]], но с дополнительной памятью <tex>O(|s|\cdot \log(|s|)</tex>. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..i + l]</tex> и <tex>s[j..j + l]</tex>. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной <tex>2^k</tex>, где <tex>k = \lfloor \log{l} \rfloor</tex>. Тогда наши строки совпадают, если <tex>c[k][i] = c[k][j]</tex> и <tex>c[k][i + l - 2^k] = c[k][j + l - 2^k]</tex>.
+У хешей есть один недостаток {{---}} коллизии, возможно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]], но с дополнительной памятью <tex>O(|s|\cdot \log(|s|))</tex>. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..i + l]</tex> и <tex>s[j..j + l]</tex>. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной <tex>2^k</tex>, где <tex>k = \lfloor \log{l} \rfloor</tex>. Тогда наши строки совпадают, если <tex>c[k][i] = c[k][j]</tex> и <tex>c[k][i + l - 2^k] = c[k][j + l - 2^k]</tex>.
 Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(|s|))</tex> на запрос, если предподсчитать все <tex>k</tex>, то <tex>O(1)</tex>.
@@ Строка 39: / Строка 39: @@
 *[[Суффиксный массив]]
 *[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
 ==Источники информации==

@@ Строка 1: / Строка 1: @@
 {{Шаблон:Задача
 |definition =
-Пусть дана строка <tex>s</tex>, требуется посчитать количество [[Основные_определения,_связанные_со_строками#palindrome | палиндромов]] в ней за <tex>O(|s|\cdot\log{|s|)}</tex> c помощью хешей.
+Пусть дана строка <tex>s</tex>, требуется посчитать количество [[Основные_определения,_связанные_со_строками#palindrome | палиндромов]] в ней.
 }}
 == Алгоритм ==
 === Идея ===
-Рассмотрим сначала задачу поиска палиндромов нечетной длины. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом. Поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]].  Для сохранения асимптотики проверку совпадения левой и правой половины требуется выполнить за <tex>O(1)</tex>. Для этого можно воспользоваться методом хеширования.
+Рассмотрим сначала задачу поиска палиндромов нечетной длины. Для каждой позиции в строке <tex>s</tex> найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка <tex>t</tex> является палиндромом, то строка полученная вычеркиванием первого и последнего символа из <tex>t</tex> также является палиндромом, поэтому длину палиндрома можно искать [[Целочисленный_двоичный_поиск | бинарным поиском]]. Проверить совпадение левой и правой половины можно выполнить за <tex>O(1)</tex>, используя метод хеширования.
 Для палиндромов четной длины алгоритм такой же, только следует проверять вторую строку со сдвигом на единицу, при этом мы не посчитаем никакой палиндром дважды из-за четности-нечетности палиндромов.
@@ Строка 13: / Строка 13: @@
   '''int''' binarySearch(s : '''string''', center, shift : '''int'''):
       ''<font color=green>//shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1</font>''
-      '''int''' l = -1, r = s.length, m = 0
+      '''int''' l = -1, r = min(center, s.length - center + shift), m = 0
       '''while''' r - l != 1
           m = l + (r - l) / 2
@@ Строка 27: / Строка 27: @@
           ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)
       '''return''' ans
 === Избавление от коллизий ===
-У хешей есть один недостаток {{---}} коллизии, у двух разных строк хеши могут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]]. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..i + l]</tex> и <tex>s[j..j + l]</tex>. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной <tex>2^k</tex>, где <tex>k = \lfloor \log{l} \rfloor</tex>. Тогда наши строки совпадают, если <tex>c[k][i] = c[k][j]</tex> и <tex>c[k][i + l - 2^k] = c[k][j + l - 2^k]</tex>.
+У хешей есть один недостаток {{---}} коллизии, возможно подобрать входные данные так, что хеши разных строк будут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью [[Суффиксный массив | суффиксного массива]], но с дополнительной памятью <tex>O(|s|\cdot \log(|s|)</tex>. Для этого построим суффиксный массив для строки <tex>s + \# + reverse(s)</tex>, при этом сохраним промежуточные результаты классов эквивалентности <tex>c</tex>. Пусть нам требуется проверить на совпадение подстроки <tex>s[i..i + l]</tex> и <tex>s[j..j + l]</tex>. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной <tex>2^k</tex>, где <tex>k = \lfloor \log{l} \rfloor</tex>. Тогда наши строки совпадают, если <tex>c[k][i] = c[k][j]</tex> и <tex>c[k][i + l - 2^k] = c[k][j + l - 2^k]</tex>.
-Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(|s|)</tex> на запрос, если предподсчитать все <tex>k</tex>, то <tex>O(1)</tex>.
+Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и <tex>O(\log(|s|))</tex> на запрос, если предподсчитать все <tex>k</tex>, то <tex>O(1)</tex>.
 ==См. также==

← Предыдущая		Версия 16:41, 19 марта 2016
Строка 26:		Строка 26:
	ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)		ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)
	'''return''' ans		'''return''' ans
		+
		+	==См. также==
		+	*[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
		+
		+	[[Категория:Алгоритмы и структуры данных]]
		+	[[Категория:Суффиксный массив]]