Ответ 1
Некоторые мысли и частичный ответ на меня:
Наихудший случай для алгоритма грубой силы:
a^(n+1) b в (a^n b)^m
например. aaab в aabaabaabaabaabaabaab
Наихудший случай для SMOA:
Что-то вроде yxyxyxxyxyxyxx в (yxyxyxxyxyxyxy)^n. Требуется дальнейшая доработка. Я пытаюсь обеспечить, чтобы каждое продвижение составляло только половину длины частичного совпадения, и для вычисления максимального суффикса требуется максимальная сумма обратного отслеживания. Я уверен, что я на правильном пути, потому что этот тип случая - единственный способ, который я нашел до сих пор, чтобы моя реализация SMOA (асимптотически 6n+5) выполнялась медленнее, чем glibc Two-Way (что асимптотически 2n-m, но имеет умеренно болезненные служебные данные предварительной обработки).
Самый худший случай для чего-то подвижного хеша:
Любая последовательность байтов вызывает хеш-столкновения с хешем иглы. Для любого разумно быстрого хэша и заданной иглы должно быть легко построить стог сена, чей хеш сталкивается с хешей иглы в каждой точке. Однако, кажется, трудно одновременно создавать длинные частичные совпадения, которые являются единственным способом получить наихудшее поведение. Естественно, что при худшем случае игла должна иметь некоторую периодичность и способ эмуляции хэша путем настройки только конечных символов.
Наихудший случай для двухстороннего:
Кажется, очень короткая игла с нетривиальным разложением MS - что-то вроде bac - где стог сена содержит повторяющиеся ложные срабатывания в правой половине компонента иглы - что-то вроде dacdacdacdacdacdacdac. Единственный способ, которым этот алгоритм может быть медленным (за исключением того, что авторы glibc плохо его реализуют) заключается в том, что внешний цикл повторяется многократно и неоднократно подвергается этим накладным расходам (и делает значительную нагрузку на настройку).
Другие алгоритмы:
Мне действительно интересны только алгоритмы, которые O(1) в пространстве и имеют низкую нагрузку на предварительную обработку, поэтому я не рассматривал их наихудшие случаи. По крайней мере, Бойер-Мур (без модификаций сделать его O(n)) имеет нетривиальный худший случай, когда он становится O(nm).