Проверка слова на маску.

[Null]

А у формы AA разве есть автомат?

[Circiter]

2Null
Если вам все-таки не хочется самостоятельно возиться с разбором строчек, просто воспользуйтесь регулярными выражениями, например из perl'а. К примеру, ваш паттерн AA соответствует регэксу (.*)\1 ну и т.д. Да, словосочетание "регулярные выражения" здесь не совсем к месту, просто терминология устоялась. :) Конечно, автоматный подход здесь просто так не применишь, да и временная асимптотика экспоненциальна, но это в теории, на деле (для большинства шаблонов) все шустро работает.

[venco]

Вы полагаете Perl чудесным образом быстро посчитает?

[Circiter]

Я добавил там в сообщение немножно про экспоненциальное время. :)

[Null]

Я про алгоритм спрашиваю. Да и задачи на олимпиадах в перле не принимают. Ну и не знаю я его.

[Circiter]

2Null

Цитата:

Да и задачи на олимпиадах в перле не принимают. Ну и не знаю я его.

Ну что вы к perl'у-то прикопались, я же просто пример привел. Уж grep-то у вас всегда под рукой есть.

Цитата:

Я про алгоритм спрашиваю.

Можно почитать исходники любой ERE-совместимой программульки, e.g., того же grep'а (там регулярные выражения даже круче реализованы чем в perl'е).

Для этого используется бэктрэкинг (+динамическое программирование). Мне показалось, что можно для оптимизации использовать вещи вроде Z-функции, суффиксных деревьев, &c. :)

[Null]

В грепе и ждаве регулярными выражениями называются другие, по-моему там проверка проще будет. Бэктрэкингом вы перебор обозвали?

[Circiter]

Но grep все-таки умеет работать с perl- и вообще ere-выраженияими, вроде того же (.*)\1.

У вас же есть google и такой дядька как Russ Cox, почитайте его отжиги. :)

[Null]

Ничего найти не могу.

[Circiter]

Ну вот например:

1. Russ Cox, Regular Expression Matching Can Be Simple And Fast,
2. Regular Expression Matching: the Virtual Machine Approach,
3. Regular Expression Matching in the Wild.

Особенно вторую часть посмотрите.

Про бэктрэкинг, Z-функцию и суффиксные деревья информация есть в википедии (наверное). Исходники grep'а по прежнему стоит почитать (только надо найти правильную версию с поддержкой ere выражений).

[Null]

В ваших ссылках ничего похожего а разбор AA нету.