нет, нам нужны частичные суммы хешей. К примеру, если нужно узнать сумму на подотрезке, Вы делаете массив частичных сумм и тогда за О(1) узнаете ответ, неважно какой длины запрашивается отрезок.
Так же и здесь — сделать массив частичных сумм хешей и для любого M конкретный хеш извлекается за O(1)
Вы сами строите хеш-функцию.
Скажем F(pos) = Spos * p0 + Spos+1 * p1 +… + Spos+M-1 * pM-1
для pos = 0..|S|-M
p — простое число. желательно первое после количества букв в алфавите, тоесть 29 или 31. Функцию можно взять по модулю большого числа. Преподсчитываем за линию еще до вычислений для обоих строк.
Теперь, когда мы берем подстроку строки S2 — это преподсчитанное значение нашей функции. O(1). Нужно определить, в каких позициях это число находится в строке S. Это тривиально, так как работаем мы уже с числами, а не со строками.
Можно искать проекции хешированием. Поскольку у нас фиксированная длинна M, можно преподсчитать все хеши подстрок S2 длины M, а потом при проверке высчитать хеш нужной для проекции строки и сразу узнать позиции. Итого — O(|S2|) на препроцесс и O(M+log|S2|)
Еще одним последствием приглушения эмоциональности является искажение восприятия внешнего мира. Без радости, любви, печали или злости — он превращается в техногенный, серо-зеленый мир Матрицы. Работа, сон, работа… Сдается мне что такая ситуация будет мало кого радовать.
мне кажется, здесь Вы перегнули. Эмоций меньше — это правда, но меньше эмоций от тех вещей, которые вызывают эмоции у других. Например, у меня фракталы и их связь с реальным миром вызывают бурю эмоций. Астрономия, космос, математика в реальной жизни, все это лично у меня провоцирует шторм внутри.
Просто акценты и приоритеты меняются
Ну, во-первых, как уже здесь писали, абсолютная погрешность чисел Стирлинга стемится к бесконечности.
Во-вторых, я как раз к этому и веду, что при ограничениях можно как-то выкрутиться. Даже для тысячи, пускай не Вашим методом. А при их отсутствии всякие константы на размерность чего-либо теряют смысл.
практически в любой задаче есть ограничения. Скажем, вычыслить n!.. 0<=n<=1000
поэтому в теории получается фиксированное количество операций. А если ограничений в задаче нету — тогда действительно невозможно
поскольку в реализации циклов условные операторы должны использоваться — то любую задачу, где количество итераций не константно, невозможно решить без условных операторов? (например тот же факториал)
Так же и здесь — сделать массив частичных сумм хешей и для любого M конкретный хеш извлекается за O(1)
Скажем F(pos) = Spos * p0 + Spos+1 * p1 +… + Spos+M-1 * pM-1
для pos = 0..|S|-M
p — простое число. желательно первое после количества букв в алфавите, тоесть 29 или 31. Функцию можно взять по модулю большого числа. Преподсчитываем за линию еще до вычислений для обоих строк.
Теперь, когда мы берем подстроку строки S2 — это преподсчитанное значение нашей функции. O(1). Нужно определить, в каких позициях это число находится в строке S. Это тривиально, так как работаем мы уже с числами, а не со строками.
мне кажется, здесь Вы перегнули. Эмоций меньше — это правда, но меньше эмоций от тех вещей, которые вызывают эмоции у других. Например, у меня фракталы и их связь с реальным миром вызывают бурю эмоций. Астрономия, космос, математика в реальной жизни, все это лично у меня провоцирует шторм внутри.
Просто акценты и приоритеты меняются
Во-вторых, я как раз к этому и веду, что при ограничениях можно как-то выкрутиться. Даже для тысячи, пускай не Вашим методом. А при их отсутствии всякие константы на размерность чего-либо теряют смысл.
есть
поэтому некоторые класс таких задач уже можно решать подобным образом
int Rec(int n)
{
int a = -isPos(n);
return a&(n*Rec(n-1))+1-isPos(n);
}
isPos можно без ифов реализовать.
а так условных операторов вообще нету
return (a&b);
и a равно нулю, то b не вычисляется. рекурсия спасает
printf("%s", isCake(s)?«Yummy»:«Lie!!»);
В основе все равно if
а у Вас их многовато)
поэтому в теории получается фиксированное количество операций. А если ограничений в задаче нету — тогда действительно невозможно