Сложность одного алгоритма

[realeugene]

ТС так и не ответил, откуда эта задача. Можно ли ему помогать?

Мне кажется, сам ТС не очень понимает формулировку заданной ему задачи:

gogoshik в сообщении #1524514 писал(а):

Выдаст $zz$, то есть что "сокращения не существует".

Что мешает сократить строку до пустой?

[mihaild]

realeugene в сообщении #1524694 писал(а):

Мне кажется, сам ТС не очень понимает формулировку заданной ему задачи

Это был пример, на котором предложенный им алгоритм работает неправильно.

[matemat]

realeugene в сообщении #1524694 писал(а):

Можно ли ему помогать?

Можно. Помогайте.

Тут нужно искусство решить задачу, а в чем хитрость не понять эту задачу?

-- 30.06.2021, 01:10 --

realeugene в сообщении #1524559 писал(а):

Алфавитом обычно называют фиксированное в задаче константное множество. А у вас нечто иное.

Алфавитом называется конечное непустое множество. Его элементы называются символами или буквами.

У ТС:

gogoshik в сообщении #1524505 писал(а):

Пусть $s$ -- конечная строка символов произвольного алфавита

Где противоречие?

[realeugene]

matemat в сообщении #1524767 писал(а):

Можно. Помогайте.

Вы ТС? Нет? Он так и не ответил, откуда задача. Задача уровня тестовой.

[Mihaylo]

mihaild в сообщении #1524693 писал(а):

Что этот вариант алгоритма выдаст на строке $abcdacbd$?

Алгоритм подсчитает число спутанных пар символов:
ab - спутана
ac - спутана
ad - спутана
bc - не спутана
bd - спутана
cd - спутана

Да, действительно... Надо строить некоторое дерево спутанности, в котором в корне лежит исходная строка, в которой потенциально могут спутанные символы. По мере нахождения спутанных символов выстраивать ветви дерева. При этом, если высота дерева превышает 4 (?), то алгоритм завершается...

[realeugene]

В общем, приведу линейный алгоритм без деталей реализации и доказательств.

Рассматриваем символы строки по одному. Если рассматриваемый символ второй в паре, и предыдущий оставшийся в строке символ совпадает со следующим оставшимся символом для первого символа его пары, удаляем из строки эту пару символов.

В конце проверяем оставшуюся строку на совпадение с одним из трёх шаблонов конечной длины.

[realeugene]

Только местоимение "его" лучше выкинуть, получилось неоднозначно.

[Mihaylo]

Проверяйте свой алгоритм на строках:
abacdeebdfcf
aabcbdefedfc
abcabdcdefef

[realeugene]

Mihaylo в сообщении #1524867 писал(а):

Проверяйте свой алгоритм на строках:

Спасибо. Действительно, чрезмерная оптимизация привела к багу. Нужно добавить условие, что равные друг другу соседи - это разные символы, а не один и тот же символ строки.