I
суфмас можно за линию, но это сложно
Да, знаю. Но просто за н лог н, я про это.
Size: a a a
2020 May 26
CD
собственно, для автомата состояние это подстрока входной строки
таких подстрок квадрат, но они сжаты по принципу "одинаковые"
I
собственно, для автомата состояние это подстрока входной строки
но нужно, чтобы в разных индексах, она была разной.
I
Я подумаю. Автоматы то я вкурил. Ну в общем, на лету я не схватываю. Но думаю, что сзвачу, за некоторое время.
CD
я не до конца уверен, но по-моему ты в проверке на равенство букв просто знаешь свою эталонную позицию
I
я не до конца уверен, но по-моему ты в проверке на равенство букв просто знаешь свою эталонную позицию
вот если знаю, тогда, так как ты говоришь, сделать можно.
CD
ну каждое состояние автомата в сжатом смысле это набор суффиксов одной подстроки
CD
и ты знаешь правую границу этих суффиксов
I
Мне просто время на подумать нужно. Но я все ещё не все, то есть, могу ещё написать, если что-то не пойму. Спасибо, что Выручаешь. Просто большое спасибо.
CD
Мне просто время на подумать нужно. Но я все ещё не все, то есть, могу ещё написать, если что-то не пойму. Спасибо, что Выручаешь. Просто большое спасибо.
да, если что у тебя должна быть какое-то прямо много запросов, иначе простейшими хешами можно каждый отработать
CD
тут скрытые константы всегда большие за асимптотиками
I
да, если что у тебя должна быть какое-то прямо много запросов, иначе простейшими хешами можно каждый отработать
а как хешами решать? Материал на почитать есть.
I
Что то типа Рабина Карпа?
CD
а как хешами решать? Материал на почитать есть.
там если ты ищешь что-то не очень частое, ты просто берешь оконные схемы с хешами типа * 625 mod 2^64
CD
или даже ксоры отрезка
CD
это зачастую лучше, чем в препроцессоре пару раз дернуть аллокатор на каждую букву
CD
учитывая, что, кажется, локализация подстроки как состояния потребует бинпоиска или еще каких-то препроцессов, на практике очень хочется иметь либо суфмассив, либо решать втупую
I
Ну вот я думаю о суффмассиве.
CD
ну там эта структура строится за счет lcp соседних после построения сортированной версии
CD
и тебе надо бинпоиском найти отрезок всех по эталону