Регулярки и автоматы хороши, когда вам требуется найти все подстроки, принадлежащие к некоторому классу (например, выделить из текста все даты в каком-то формате). Для вашей же задачи и в более общем случае (когда длина шаблона может быть большой) существуют более простые и при этом не менее эффективные алгоритмы, например алгоритм Кнута-Морриса-Пратта
Если экономить память — то нужно хранить последние m символов в кольцевом буфере
Не обязательно, можно банально каждый раз сдвигать символы на 1 элемент влево. Вообще, если дело обстоит так, как вы описали выше, и у вас всего 4 возможных символа, то любую строку длины 4 можно представить просто числом от 0 до 15 и сравнение строк свести к сравнению двух чисел.
В принципе всё это решаемо, но по итогам я подумал что собственный ДКА будет компактнее.
Мне кажется, тут вы ошиблись, тривиальный алгоритм займет меньше строк, чем одно лишь описание автомата для вашей строки.
В чем минус вашего решения на мой взгляд? Представим себе, что мы захотели поменять шаблонную строку или добавить новую. В этом случае мы не можем просто где-то заменить константу, а вынуждены будем руками реализовывать конечный автомат для нашей новой строки. Дело это не такое уж и тривиальное, как кажется, представим, что у нас строка вида "ABAC" и мы находимся в состоянии «встречено первые 3 символа». Тогда для символа A мы должны перейти в состояние «встречен 1 символ», для B — «встречено 2 символа», для С — «найдена вся строка», для D — «ни один символ не встречен». Если хотите, можно, увеличив длину строки, построить ещё более сложный пример.
С точки зрения регулярных выражений задача проста — ищем во входной строке подстроку «ACDA».
Если ваша задача звучит именно таким образом, то не очень понятно, зачем вам здесь регулярные выражения или собственная реализация конечного автомата. Задача поиска подстроки в строке является классической, известно множество алгоритмов её решения, в вашем случае, если строка-образец действительно такая короткая, подойдет тривиальный алгоритм, работающий за O(nm), где n — длина строки, в которой ищем, а m — длина образца.
Мне кажется, что в первом вопросе "Move semantics" лучше было перевести как "семантика перемещения" (либо так и оставить "move-семантика") вместо "семантики переноса".
И ещё, второго вопроса из английской версии нету ни в русском варианте, ни в видео-интервью.
На мой взгляд, стоило бы лучше рассказать про какую-то другую часть библиотеки. Обработка текста посимвольно — достаточно тривиальная и неинтересная задача.
Интересно. Но что-то я не могу прикинуть в уме асимптотику — у нас получается же O(n) амортизированное?
Если вы про теоретическое описание, то нет, никакой амортизационный анализ не применяется, каждый запрос выполняется строго за O(1), об этом даже где-то по тексту написано. Если же вы про мою реализацию, то да, там в силу использования вектора для хранения очередей, каждый push или pop выполняется за амортизированное O(1). Естественно, можно обойтись и без него, например, используя односвязный список и выдавая указатель на его элемент вместо числового id, я использовал вектор для упрощения и соответствия интерфейсу теоретического описания.
И какой порядок константы перед этим самым n?
В каких единицах надо это оценить?
Начиная с какого порядка размера очереди она начнёт выигрывать по производительности у O(n*log(n)), которая явно проще в реализации?
Что вы имеете в виду под простой реализацией за O(n log n): реализацию с помощью персистентного дерева поиска по неявному ключу? По-хорошему, надо просто написать и сравнить. Но осмелюсь предположить, что на данных, при которых эти реализации будут быстрее наивной за n2, мой алгоритм всегда будет выигрывать. Почему я так считаю? Потому что при добавлении или удалении вершины из персистентного дерева (операции push и pop, соотвественно), мы вынуждены будем создать копию каждой вершины на пути до корня. А на таких данных, длина этого пути будет не меньше 10 (она порядка log n). Впрочем, это лишь гипотеза. К слову, я не считаю её явно проще в реализации, она скорее проще в понимании, потому что от неперсистентного варианта почти не отличается, объем же кода будет примерно одним и тем же.
Я не профессионал в этой области, просто делюсь своим впечатлением. Мне, как читателю, формулировка «Отловить проще всего по желанию вернуться к началу предложения и абзаца и перечитать ещё раз» нравится больше, чем «К счастью, определить эти точки просто. Если вдруг вы захотите вернуться к началу предложения и перечитать — вот она, проблема» именно за счет большей сжатости без какой-либо потери смысла. Единственное, глаз немного спотыкается на двух «и» подряд, относящихся к разным частям.
Мне кажется, тут вы ошиблись, тривиальный алгоритм займет меньше строк, чем одно лишь описание автомата для вашей строки.
В чем минус вашего решения на мой взгляд? Представим себе, что мы захотели поменять шаблонную строку или добавить новую. В этом случае мы не можем просто где-то заменить константу, а вынуждены будем руками реализовывать конечный автомат для нашей новой строки. Дело это не такое уж и тривиальное, как кажется, представим, что у нас строка вида "ABAC" и мы находимся в состоянии «встречено первые 3 символа». Тогда для символа A мы должны перейти в состояние «встречен 1 символ», для B — «встречено 2 символа», для С — «найдена вся строка», для D — «ни один символ не встречен». Если хотите, можно, увеличив длину строки, построить ещё более сложный пример.
И ещё, второго вопроса из английской версии нету ни в русском варианте, ни в видео-интервью.
В каких единицах надо это оценить?
Что вы имеете в виду под простой реализацией за O(n log n): реализацию с помощью персистентного дерева поиска по неявному ключу? По-хорошему, надо просто написать и сравнить. Но осмелюсь предположить, что на данных, при которых эти реализации будут быстрее наивной за n2, мой алгоритм всегда будет выигрывать. Почему я так считаю? Потому что при добавлении или удалении вершины из персистентного дерева (операции push и pop, соотвественно), мы вынуждены будем создать копию каждой вершины на пути до корня. А на таких данных, длина этого пути будет не меньше 10 (она порядка log n). Впрочем, это лишь гипотеза. К слову, я не считаю её явно проще в реализации, она скорее проще в понимании, потому что от неперсистентного варианта почти не отличается, объем же кода будет примерно одним и тем же.