Соответствие шаблону: соответствие строкам с рисунком

Question

Я пытался сопоставить шаблон внутри строки. У меня заканчиваются идеи, как это сделать на Java с хорошей временной сложностью. не

Нет его не простое соответствие регулярного выражения (но любило быть опровергнут)

То, что я пытаюсь это,

Pattern: "1221" (Средства 1 слово повторяется один раз, второе слово повторяется дважды, последнее слово совпадает с первым словом)

Действительных Входной: «aabbbbbbaa» (аа происходит в начале и в конце, в то время как средняя часть занята БББОМ повторять дважды)

Я попытался следующие подходы, но с треском провалился

• Я попытался петля ввод с рисунком. Но это не решило проблему, хотя с большим количеством циклов я могу ее достичь, но она увеличивает временную сложность экспоненциально.
• Пробная рекурсия и снова бесполезно.

Какие еще подходы я могу попробовать?

Я думаю, что динамическое программирование может быть ответом, но я не могу определить условие завершения.

Любая помощь будет оценена по достоинству.

Answer 1

Вы можете использовать простые регулярные выражения, например:

^(.+)(.+)\2\1$ 

Это именно то, что и хотят: