Вообще, не обязательно состояния детерменированного НКА нумеровать именно так - битовой маской. Это лишь один из вариантов.
Если вводить тут концепцию детерминизации НКА, то это только запутывает. Суть-то не в том, чтобы получить состояние в виде одного числа. Суть в том, чтобы все вычисления делать одной битовой операцией.
Да, можно считать, что тут идет работа с ДКА, у которого вместо таблицы рассчитываются состояния. Но ведь так можно смотреть и на вообще любой НКА. Вместо таблицы с 2^n состояний тут по какому-то алгоритму идет рассчет нового состояния (хоть и с использованием таблицы на n состояний)
И вообще, на любую программу можно смотреть как на машину тьюринга. Концептуально одно и тоже, но смысла в этом маловато. Даже если какая-то оптимизация алгоритма вводит переходы чего-то влево/вправо и какие-то таблицы.
Еще есть игры серии X. Последняя X4 Foundation вышла недавно относительно. Но и в первых трех экономика симулируется весьма серъезно. Там можно понастроить фабрик и уронить цену ресурса почти в ноль. Можно уничтожить фабрики фракции в окресности, ресурса станет мало и цена взлетит в облака.
Имеются, куча уязвимостей обнаружены и закрыты, неизвестно сколько еще даже не обнаружены. Хром не является каким-то особо дырявым решетом, уязвимости регулярно находят практически во всех достаточно популярных приложениях. И когда новая уязвимость будет открыта, если хром не запущен от администратора, то последствия ее эксплуатации будут меньше.
Нет. x дает квадртаичный вычет - полный квадрат. Т.е. x^2 - дает полный квадрат по модулю N. т.е. x^2 = k^2 (mod N), k^2 < N.
Отсюда уже следует, что x^2 = mN+k^2 для какого-то m. Просто по определению остатка от деления. Если x - не тривиальный (КВК как его называет автор), то m>0.
Для 33 ответ уже был (признаки делимости используются в любой атаке)
Но ведь 33 - это лишь пример, в котором ваши частные случаи не сработали. Если вы эти частные случаи опишите, я вам могу и 15-значное число найти, которое под них не подходит, где признаки делимости не сработают.
В прошлых статьях вы не указывали, что в общем случае у вас будет перебор для поиска КВК, а лишь фокусировались на удачных примерах. Для 33 методы из ваших примеров не работали и это должно было или заставить вас описать другой частный случай, или признать перебор. Тут вы уже перебор признали, так что 33 уже не так важно.
Как только поймете ЗРД, дойдет, что даже перебор не требует числа корня из N, а существенно меньше.
Тривиальный перебор тоже не всегда требует корня из N. Он идет до минимального из двух делителей p и q. В худшем случае это может быть примерно до конрня из N.
ЗРД - это про то что КВК в центре с двумя числами, кратными делителям N? Это очевидный факт, показанный в формулах в моем комментарии выше: https://habr.com/ru/articles/908714/comments/#comment_28306208. Да, если у вас есть КВК, ясно как его использовать для получения делителей. ЗРД у вас нигде не говорит о распределении КВК, как далеко они друг от друга расположенны и как долго их искать.
Для 77, вы пишите:
Первый КВК = 4 примыкает к ТКВК.
За ТКВК идет 9. Вот мы уже знаем, что 9^2 = 4 (mod 77), или 9^2 = N+4. Отсюда сразу можно найти N=9^2 - 2^2= (9-2)(9+2) = 7*11. Вы в тексте что-то вычисляете в ваших терминах, но это излишне запутанные терминами вычисления, которые проще, понятнее и логичнее заменить простой арифметикой выше.
Тут нам очень повезло, что КВК оказался сразу за ТКВК (иными словами, ceil(sqrt(N)) оказался КВК). Это редкий частный случай. Для чисел до миллиона из двух простых делителей таких чисел 1409 из 288533. Всего 0.4%. Для чисел до 100 миллионов этот процент снижается до 0.1%. Чем больше числа, тем реже такие удачные встречаются.
В общем случае, где за ТКВК не стоит КВК, вам придется перебирать строки вашей таблицы, чтобы найти КВК.
Вы просто описали полный перебор для поиска КВК. Нет не полный, а до 1-го РИ
Вы утверждаете, что это быстрый перебор короче корня из N в общем случае? Я этого не вижу. Могли бы вы, пожалуйста, формализовать как именно вы перебираете строки таблицы в поисках КВК в общем случае, и как-то оценить, сколько строк он переберет? Может, вы вывели какое-то ограничение на то, как далеко от начала таблицы лежит первый РИ? Пока кажется, что они встречаются раз в min(p,q) строк, поэтому поиск РИ нисколько не быстрее тривиального перебора, потому что в худшем случае min(p,q) ~ sqrt(N).
Да, именно так в теории языков и доказывают эквивалентность недетерменированных и детерменированных автоматов. И те и дургие - дают регулярные языки. Любой НКА можно превратить в ДКА с 2^M состояниями.
Простенькая переборная программа по самому наивному, известному сотни лет методу, тоже работает за доли секунды.
Можно строить не всю строку, а только левую колонку и даже глазами легко обнаружить 1, 4, 9 , и др. малые квадраты, но можно и автоматизировать этот процесс.
Вы просто описали полный перебор для поиска КВК. Это тривиальная идея. На практике обычно не используемая, потому что она не быстрее самого наивного перебора выше в общем случае.
Тут вся ваша таблица, раскраски и определения не нужны вообще. 99.99% текста из ваших статей можно взять и выкинуть, ибо они для этого не нужны вообще. Все это одна формула:
нашли такой x - можем разделить. Как искать такой x вы не придумали.
Этот пример иллюстрирует возможность факторизации любого составного числа (и 33, и 65, и пр.)
И как же раскладывается 33? Без постройки таблицы. Как вы эти интервалы решающие-то ищите?
Для модуля кольца N = 629 найти делители (разложение на простые сомножители).Решение можно получить в любом решающем интервале. Выбираем РИ, например, с центром в х = 44.
Вот как мы выибираем РИ - это и есть основной вопрос. Если вам выдать КВК, то факторизация понятно как делается. Вы тут перебором же ищите? До корня из N вариантов, похоже:
Здесь мы используем перебор строк, но не тотальный, так как квадратов в модели √N.
Так ведь тривиальный метод факторизации такой и есть: перебираем все числа до √N, смотритм, делится ли на них N. Все. Ваша модель тут вообще не нужна, ничего не ускоряет и не помогает и смысла не несет.
такого перебора можно избежать, используя свойства модели, построив зависимости переменных модели (частные случаи)
Ага, вот уже и не "модель позволяет решать проблему факторизации", а некоторые частные случаи можно по каким-то зависимостям, выведенным на частных случаях таблицы, решить.
Скажите, а вот случай, что если число заканчивается на цифру 5, то можно поделить на 5 - он достоин звания Модели? Он вообще полезен?
Что бы показать ценность вашей модели, вы не подбирайте примеры, на которых они работают, а формализуйте их, выпишите критерии в виде формул и оцените, как часто они встречаются. Например ваш пример с rccc+1 раскладывающимся на множители работает для N, т.ч. √(3N+4) - целое.
Номера жёстко привязаны к операторам связи. Операторы связи привязаны к странам, пользователь переехал - приплыли.
Во многих странах это не так. Можно запросто переехать на другого оператора с сохранением номера. Вроде даже в россии это теперь возмножно, не изучал вопрос, но какие-то новости слышал. Крайний случай переезда в другую страну весьма редок. Кроме того. номер можно поменять в настройках.
Вот то, что смс и безопасность вообще не пересекаются и кто угодно может получать какие угодно смс с весьма простым оборудыванием - это беда, да.
Зато номера телефонов очень удобно сшивать с другими личными данными и продавать. Это единственное преимущество SMS.
Не только, это еще и минимальная защита от ботов. Ибо номера получать на порядки дороже и сложнее почти любого другого метода.
Вы неправильно понимаете потребление памяти. Вы ее зачем купили, чтобы любоваться на нее? Память должна работать. Физическая память в винде - это фактически еще один уровень кеша над файлом подкачки. Соответственно, какой-то причины постоянно все из нее выгружать, только чтобы она выглядела незаполненной, вообще нет.
Было бы у вас только 32 Гб памяти, винда бы держала ее заполненной на условные 25гб вместо 43.
Нет. Большая часть неоптимальности в не бесплатных абстракциях: фреймворки на фреймворках, завернутые библиотеки и эмуляцию. Вот, например, приложения на электроне. Тормозят, потому что это целый браузер для каждого приложения, интерпретирующий джаваскрипт. Завести сюда оптимизацию - это надо разрабатывать отдельно веб приложение и нативные приложения под каждую систему. Это нужно в 4 раза раздуть штат, набрать специалистов по нескольким языкам программирования, поддерживать похожий код в 4-ех местах, инфрастурктуру под это все и много много отладки багов, потому что, например, только на этой условной версии MacOs что-то отваливается в приложении.
И тоже самое в играх. Можно взять готовый unreal engine и не разбрабатывать огромной командой десять лет свой движок. Можно впендюрить люмены и наниты и не расставлять освещение руками во всех уровнях, сэкономив человеко-годы работы и зарплаты. Да, это будет тормозить на не топовых видюхах из последнего поколения, но с ИИ дорисовкой кадров и растяжением картинки - люди хавают.
Так что, нет, большая часть оптимизации совсем не бесплатна.
Вот вам ДП для этой задачи (найти вхождения шаблона в тексте):
dp[i][j] - находятся ли в конце первых i символов текста первые j символа шаблона (можно ли приложить шаблон так, что в позиции i+1 текста окажется j-ый символ шаблона).
Например, если текст "abacaba" а шаблон "aba", то dp будет:
{{1,0,0,0}, // ноль символвов в тексте. можно приложить только 0 из шаблона
{1,1,0,0}, // текст - "a". Можно приложить "" и "a"
{1,0,1,0}, // текст "ab". Можно пиложить "" и "ab"
{1,1,0,1}, // к "aba" можно приложить "a" и "aba"
{1,0,0,0}, // текст "abac" - ни "a", "ab", "aba" приложить нельзя.
...
}
Обратите внимание dp - это мы прикладываем кусок шаблона к куску текста в конце текста.
Ясно, что если dp[i][len(pattern)] == 1 - то мы нашли вхождение. К какому-то куску текста приложили весь шаблон.
База: dp[i][0] = 1, dp[0][j] = 0
Переход: dp[i][j] = (text[i-1] == pattern[j-1]) & dp[i-1][j-1]. Можем приложить, только если последние символы совпали и левее можно приложить оставшуюся часть.
Вот одна строка этого ДП - это и есть биты с которыми работает алгоритм. Длина строки матрицы = длине шаблона+1 = количеству состояний в автомате.
Можно пересчитывать ДП двумя циклами, а можно заметить, что все операции (text[i-1] == pattern[j-1]) & dp[i-1][j-1] можно подсчитать одной битовой операцией, если кажду строку матрицы хранить в битовой маске. Берем строку для dp[i-1], сдвигаем и зануляем все биты, где (text[i-1] != pattern[j-1]).
Далее, вот эти зануляемые биты, там от i зависит только text[i-1]. Т.е. если в разных позициях i в тексте один и тот же символ, то мы занулим одни и те же биты в строке матрицы. Поэтому можно предподсчитать все позиции j, для которых для данного символа алфавита условие выполняется. Это и есть маски для символов. В итоге, вместо цикла по j надо лишь сделать dp[i] = (dp[i-1] << 1) & mask[text[i-1]];
Ну и, храним только последнюю строку в dp.
Но это без зведочек в шаблоне, со зведочками чуть-чуть сложнее вычисления. Будет dp[i][j] = ((text[i-1] == pattern[j-1]) & dp[i-1][j-1]) || (pattern[i-1] == '*' & (dp[i-1][j-1] | dp[i-1][j]))
Тут также все можно вычислить за несколько битовых операций.
Вот это ДП эквивалентно автомату. Тут в каждой строке 1 означает активное состояние автомата после i символов. Пересчет ДП - это изменение активных состояний.
Например строка abc, это что? 000, 001, 010, 011, 100, 101, 110, 111?
000 означает, что мы ничего не нашли. 001 - нашли c, 010 - b, 011 - нашли b и c (это невозможно для этой строки, ибо текст не может одновременно оканчиваться на b и c)...
Давайте с другой стороны: вы знакомы с динамическим программированием?
У нас K состояний в автомате. По длине строки шаблона (что ищем). Каждое может быть активно или нет. Каждому состоянию соотвествует один бит.
Каждое состояние означает, что сейчас вот в этом месте текста можно приложить шаблон до вот этого символа. Вот на картинке выше активны состояния 1 и 3. Состояние 1 означает, что к тексу сейчас можно приложить "ab". Состояние 3 - "abab". Если актвно последнее состояние - вы можете приложить всю искомую строку и нашли совпадение.
Когда обрабатываем следующий символ текста, надо взять активные состояния, из которых следующий символ как в тексте, и сделать активными следующие состояния. Потому что в них происходит переход.
Простая реализация: циклом по всем состояниям прошлись, проверили. что оно активно и посмотрели, какой там символ нужен. Но раз состояний не более 64, можно это все заменить битовыми операциями.
Множество активных состояний хранится в битовой маске
Если М не равно А то мы знаем только о неравенстве, о каких состояниях речь?
По букве М мы должны взять все состояния, которые активны и из которых есть переход по М. И сделать оттуда переход. Активные состояния, из которых нет перехода из М никуда не переходят.
В каком шаблоне?
Строка, которую мы ищем
За этими фразами скрывается какой-то механизм, который я и не понимаю.
Перечитайте википедию про конечные автоматы. Особенно про недетерменированные.
Тогда никуда не переходим. Ни одно состояние не становится активным. Автомат строку с М не принимает вообще, ведь ее нет в шаблоне. Суть в том, чтобы проверить, активно ли последнее состояние - значит строка нашлась. Если из состояния нет перехода то активных состояний быть не может. Можете считать, что в автомате есть состояние "тупик", из которого нет выхода (все переходы в него же) и куда ведут все переходы, которых на графике нет. Но для простоты его не рисуют и не считают.
Если автомат сравнивал входные значения с abab, то мы пришли в c
Нет. Мы пришли в 3 и 1. Потому что в конце строки abab есть ab. Автомат недетерменированный же. Помните, что состояние s всегда активно, потому что можно начать прикладывать строку с любой позиции. Поэтому 2 символа назад мы по a перешли одновременно из S и 1. Получили 0 и 2. На следующем символе b мы перешли одновременно из 0 и 2. Получили 1 и 3.
, откуда взялись эти 10101
У автора 0 - это активное состояние. На картинке красные состояния 1 и 3. Биты равны 0 в этих позициях. S в битах не хранится, ведь оно всегда активно.
При наложении маски мы получаем, из каких состояний будет переход. Потом это сдвигаем на 1 бит и получаем новые активные состояния.
Вообще, не обязательно состояния детерменированного НКА нумеровать именно так - битовой маской. Это лишь один из вариантов.
Если вводить тут концепцию детерминизации НКА, то это только запутывает. Суть-то не в том, чтобы получить состояние в виде одного числа. Суть в том, чтобы все вычисления делать одной битовой операцией.
Да, можно считать, что тут идет работа с ДКА, у которого вместо таблицы рассчитываются состояния. Но ведь так можно смотреть и на вообще любой НКА. Вместо таблицы с 2^n состояний тут по какому-то алгоритму идет рассчет нового состояния (хоть и с использованием таблицы на n состояний)
И вообще, на любую программу можно смотреть как на машину тьюринга. Концептуально одно и тоже, но смысла в этом маловато. Даже если какая-то оптимизация алгоритма вводит переходы чего-то влево/вправо и какие-то таблицы.
Еще есть игры серии X. Последняя X4 Foundation вышла недавно относительно. Но и в первых трех экономика симулируется весьма серъезно. Там можно понастроить фабрик и уронить цену ресурса почти в ноль. Можно уничтожить фабрики фракции в окресности, ресурса станет мало и цена взлетит в облака.
Имеются, куча уязвимостей обнаружены и закрыты, неизвестно сколько еще даже не обнаружены. Хром не является каким-то особо дырявым решетом, уязвимости регулярно находят практически во всех достаточно популярных приложениях. И когда новая уязвимость будет открыта, если хром не запущен от администратора, то последствия ее эксплуатации будут меньше.
Нет. x дает квадртаичный вычет - полный квадрат. Т.е. x^2 - дает полный квадрат по модулю N. т.е. x^2 = k^2 (mod N), k^2 < N.
Отсюда уже следует, что x^2 = mN+k^2 для какого-то m. Просто по определению остатка от деления. Если x - не тривиальный (КВК как его называет автор), то m>0.
Нет. Автор ускорил вычисления переходов НКА с помощью битовых масок.
Но ведь 33 - это лишь пример, в котором ваши частные случаи не сработали. Если вы эти частные случаи опишите, я вам могу и 15-значное число найти, которое под них не подходит, где признаки делимости не сработают.
В прошлых статьях вы не указывали, что в общем случае у вас будет перебор для поиска КВК, а лишь фокусировались на удачных примерах. Для 33 методы из ваших примеров не работали и это должно было или заставить вас описать другой частный случай, или признать перебор. Тут вы уже перебор признали, так что 33 уже не так важно.
Тривиальный перебор тоже не всегда требует корня из N. Он идет до минимального из двух делителей p и q. В худшем случае это может быть примерно до конрня из N.
ЗРД - это про то что КВК в центре с двумя числами, кратными делителям N? Это очевидный факт, показанный в формулах в моем комментарии выше: https://habr.com/ru/articles/908714/comments/#comment_28306208. Да, если у вас есть КВК, ясно как его использовать для получения делителей. ЗРД у вас нигде не говорит о распределении КВК, как далеко они друг от друга расположенны и как долго их искать.
Для 77, вы пишите:
За ТКВК идет 9. Вот мы уже знаем, что 9^2 = 4 (mod 77), или 9^2 = N+4. Отсюда сразу можно найти N=9^2 - 2^2= (9-2)(9+2) = 7*11. Вы в тексте что-то вычисляете в ваших терминах, но это излишне запутанные терминами вычисления, которые проще, понятнее и логичнее заменить простой арифметикой выше.
Тут нам очень повезло, что КВК оказался сразу за ТКВК (иными словами, ceil(sqrt(N)) оказался КВК). Это редкий частный случай. Для чисел до миллиона из двух простых делителей таких чисел 1409 из 288533. Всего 0.4%. Для чисел до 100 миллионов этот процент снижается до 0.1%. Чем больше числа, тем реже такие удачные встречаются.
В общем случае, где за ТКВК не стоит КВК, вам придется перебирать строки вашей таблицы, чтобы найти КВК.
Вы утверждаете, что это быстрый перебор короче корня из N в общем случае? Я этого не вижу. Могли бы вы, пожалуйста, формализовать как именно вы перебираете строки таблицы в поисках КВК в общем случае, и как-то оценить, сколько строк он переберет? Может, вы вывели какое-то ограничение на то, как далеко от начала таблицы лежит первый РИ? Пока кажется, что они встречаются раз в min(p,q) строк, поэтому поиск РИ нисколько не быстрее тривиального перебора, потому что в худшем случае min(p,q) ~ sqrt(N).
Да, именно так в теории языков и доказывают эквивалентность недетерменированных и детерменированных автоматов. И те и дургие - дают регулярные языки. Любой НКА можно превратить в ДКА с 2^M состояниями.
Простенькая переборная программа по самому наивному, известному сотни лет методу, тоже работает за доли секунды.
Вы просто описали полный перебор для поиска КВК. Это тривиальная идея. На практике обычно не используемая, потому что она не быстрее самого наивного перебора выше в общем случае.
Тут вся ваша таблица, раскраски и определения не нужны вообще. 99.99% текста из ваших статей можно взять и выкинуть, ибо они для этого не нужны вообще.
Все это одна формула:
нашли такой x - можем разделить. Как искать такой x вы не придумали.
И как же раскладывается 33? Без постройки таблицы. Как вы эти интервалы решающие-то ищите?
Вот как мы выибираем РИ - это и есть основной вопрос. Если вам выдать КВК, то факторизация понятно как делается. Вы тут перебором же ищите? До корня из N вариантов, похоже:
Так ведь тривиальный метод факторизации такой и есть: перебираем все числа до √N, смотритм, делится ли на них N. Все. Ваша модель тут вообще не нужна, ничего не ускоряет и не помогает и смысла не несет.
Ага, вот уже и не "модель позволяет решать проблему факторизации", а некоторые частные случаи можно по каким-то зависимостям, выведенным на частных случаях таблицы, решить.
Скажите, а вот случай, что если число заканчивается на цифру 5, то можно поделить на 5 - он достоин звания Модели? Он вообще полезен?
Что бы показать ценность вашей модели, вы не подбирайте примеры, на которых они работают, а формализуйте их, выпишите критерии в виде формул и оцените, как часто они встречаются. Например ваш пример с rccc+1 раскладывающимся на множители работает для N, т.ч. √(3N+4) - целое.
По какой формуле вы получили эти 2 числа?
Во многих странах это не так. Можно запросто переехать на другого оператора с сохранением номера. Вроде даже в россии это теперь возмножно, не изучал вопрос, но какие-то новости слышал. Крайний случай переезда в другую страну весьма редок. Кроме того. номер можно поменять в настройках.
Вот то, что смс и безопасность вообще не пересекаются и кто угодно может получать какие угодно смс с весьма простым оборудыванием - это беда, да.
Не только, это еще и минимальная защита от ботов. Ибо номера получать на порядки дороже и сложнее почти любого другого метода.
Вы неправильно понимаете потребление памяти. Вы ее зачем купили, чтобы любоваться на нее? Память должна работать. Физическая память в винде - это фактически еще один уровень кеша над файлом подкачки. Соответственно, какой-то причины постоянно все из нее выгружать, только чтобы она выглядела незаполненной, вообще нет.
Было бы у вас только 32 Гб памяти, винда бы держала ее заполненной на условные 25гб вместо 43.
Нет. Большая часть неоптимальности в не бесплатных абстракциях: фреймворки на фреймворках, завернутые библиотеки и эмуляцию. Вот, например, приложения на электроне. Тормозят, потому что это целый браузер для каждого приложения, интерпретирующий джаваскрипт. Завести сюда оптимизацию - это надо разрабатывать отдельно веб приложение и нативные приложения под каждую систему. Это нужно в 4 раза раздуть штат, набрать специалистов по нескольким языкам программирования, поддерживать похожий код в 4-ех местах, инфрастурктуру под это все и много много отладки багов, потому что, например, только на этой условной версии MacOs что-то отваливается в приложении.
И тоже самое в играх. Можно взять готовый unreal engine и не разбрабатывать огромной командой десять лет свой движок. Можно впендюрить люмены и наниты и не расставлять освещение руками во всех уровнях, сэкономив человеко-годы работы и зарплаты. Да, это будет тормозить на не топовых видюхах из последнего поколения, но с ИИ дорисовкой кадров и растяжением картинки - люди хавают.
Так что, нет, большая часть оптимизации совсем не бесплатна.
Вообще не вижу, как из этого получить хеш
Вы тролите! Тут все объяснения - попугайные повторения кода, только на русском языке. Поможет только тем, кто не умеет читать код.
Вот вам ДП для этой задачи (найти вхождения шаблона в тексте):
dp[i][j] - находятся ли в конце первых i символов текста первые j символа шаблона (можно ли приложить шаблон так, что в позиции i+1 текста окажется j-ый символ шаблона).
Например, если текст "abacaba" а шаблон "aba", то dp будет:
Обратите внимание dp - это мы прикладываем кусок шаблона к куску текста в конце текста.
Ясно, что если dp[i][len(pattern)] == 1 - то мы нашли вхождение. К какому-то куску текста приложили весь шаблон.
База: dp[i][0] = 1, dp[0][j] = 0
Переход: dp[i][j] = (text[i-1] == pattern[j-1]) & dp[i-1][j-1]. Можем приложить, только если последние символы совпали и левее можно приложить оставшуюся часть.
Вот одна строка этого ДП - это и есть биты с которыми работает алгоритм. Длина строки матрицы = длине шаблона+1 = количеству состояний в автомате.
Можно пересчитывать ДП двумя циклами, а можно заметить, что все операции
(text[i-1] == pattern[j-1]) & dp[i-1][j-1]можно подсчитать одной битовой операцией, если кажду строку матрицы хранить в битовой маске. Берем строку для dp[i-1], сдвигаем и зануляем все биты, где(text[i-1] != pattern[j-1]).Далее, вот эти зануляемые биты, там от i зависит только text[i-1]. Т.е. если в разных позициях i в тексте один и тот же символ, то мы занулим одни и те же биты в строке матрицы. Поэтому можно предподсчитать все позиции j, для которых для данного символа алфавита условие выполняется. Это и есть маски для символов. В итоге, вместо цикла по j надо лишь сделать
dp[i] = (dp[i-1] << 1) & mask[text[i-1]];Ну и, храним только последнюю строку в dp.
Но это без зведочек в шаблоне, со зведочками чуть-чуть сложнее вычисления. Будет
dp[i][j] = ((text[i-1] == pattern[j-1]) & dp[i-1][j-1]) || (pattern[i-1] == '*' & (dp[i-1][j-1] | dp[i-1][j]))Тут также все можно вычислить за несколько битовых операций.
Вот это ДП эквивалентно автомату. Тут в каждой строке 1 означает активное состояние автомата после i символов. Пересчет ДП - это изменение активных состояний.
000 означает, что мы ничего не нашли. 001 - нашли c, 010 - b, 011 - нашли b и c (это невозможно для этой строки, ибо текст не может одновременно оканчиваться на b и c)...
Давайте с другой стороны: вы знакомы с динамическим программированием?
У нас K состояний в автомате. По длине строки шаблона (что ищем). Каждое может быть активно или нет. Каждому состоянию соотвествует один бит.
Каждое состояние означает, что сейчас вот в этом месте текста можно приложить шаблон до вот этого символа. Вот на картинке выше активны состояния 1 и 3. Состояние 1 означает, что к тексу сейчас можно приложить "ab". Состояние 3 - "abab". Если актвно последнее состояние - вы можете приложить всю искомую строку и нашли совпадение.
Когда обрабатываем следующий символ текста, надо взять активные состояния, из которых следующий символ как в тексте, и сделать активными следующие состояния. Потому что в них происходит переход.
Простая реализация: циклом по всем состояниям прошлись, проверили. что оно активно и посмотрели, какой там символ нужен. Но раз состояний не более 64, можно это все заменить битовыми операциями.
Множество активных состояний хранится в битовой маске
По букве М мы должны взять все состояния, которые активны и из которых есть переход по М. И сделать оттуда переход. Активные состояния, из которых нет перехода из М никуда не переходят.
Строка, которую мы ищем
Перечитайте википедию про конечные автоматы. Особенно про недетерменированные.
Тогда никуда не переходим. Ни одно состояние не становится активным. Автомат строку с М не принимает вообще, ведь ее нет в шаблоне. Суть в том, чтобы проверить, активно ли последнее состояние - значит строка нашлась. Если из состояния нет перехода то активных состояний быть не может. Можете считать, что в автомате есть состояние "тупик", из которого нет выхода (все переходы в него же) и куда ведут все переходы, которых на графике нет. Но для простоты его не рисуют и не считают.
Нет. Мы пришли в 3 и 1. Потому что в конце строки abab есть ab. Автомат недетерменированный же. Помните, что состояние s всегда активно, потому что можно начать прикладывать строку с любой позиции. Поэтому 2 символа назад мы по a перешли одновременно из S и 1. Получили 0 и 2. На следующем символе b мы перешли одновременно из 0 и 2. Получили 1 и 3.
У автора 0 - это активное состояние. На картинке красные состояния 1 и 3. Биты равны 0 в этих позициях. S в битах не хранится, ведь оно всегда активно.
При наложении маски мы получаем, из каких состояний будет переход. Потом это сдвигаем на 1 бит и получаем новые активные состояния.