java模式匹配：将字符串与模式匹配

Question

我试图在一个字符串中匹配一个模式。我已经不知道如何在Java中以良好的时间复杂度实现这一点了

No its not a simple regex matching (but loved to be proved wrong)

我想说的是

模式：“1221”（表示一个单词重复一次，第二个单词重复两次，最后一个单词和第一个单词相同）

有效输入：“aabbbbbbaa”（aa出现在开头和结尾，中间部分被重复两次的bbb占据）

我尝试了以下方法，但失败得很惨

• 我试图用模式循环输入。但这并没有解决问题，虽然我可以通过更多的循环实现它，但它会以指数方式增加时间复杂度
• 尝试了递归，但又没有用

我还可以尝试其他方法吗

我认为动态规划可能是答案，但我无法确定终止条件

任何帮助都将不胜感激

Answer 1

您可以使用简单的正则表达式，例如：

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

它正是你想要的：