python - 正则表达式根据子字符串的长度获取字符串

Question

您能否建议是否可能以及如何为下一个问题定义正则表达式：

我有 2 个由分隔符连接的“二进制”字符串。假设分隔符始终为 3。

输入数据示例：

11000031000111011001101111
0111000301000111011001101111
001310001110110011011110

在分隔符的右侧，我需要选择所有 '1+' blob，但我不想在分隔符的左侧选择长度等于 1+ blob 的 1+ blob。

例如，在这个输入上：

11000031000111011001101111

有这些 1+ blob：

left: 11
right: 1, 111, 11, 11, 1111

我需要选择所有正确的 1+ blob，但 '11'，因为它们也存在于左侧。

所以在那个例子中我需要匹配：1,111,1111

其他示例：

0111000301000111011001101111 ==> 1,11,11,1111
001310001110110011011110     ==> 111,11,11,1111

我还需要知道每个字符串的位置（匹配对象）。了解此任务的复杂性以及是否可以构建 FSM 非常重要。如果限制左侧部分的大小（例如 < 8）怎么办

标签： pythonregex

Answer 1

由于您不仅特别要求正则表达式，而且要求有限状态机，因此我可以特别证明这是不可能的。在有限状态机中，您必须有一些有限数量的n状态。1对于在 3 的左侧找到的每个长度的 s 序列，我们需要一个状态。由于我们可以有无限多个可能长度的1s 序列，因此不可能在有限多个状态中编码此信息。

如果你特别限制了左边部分的大小，你就有效地限制了一个1s 序列的最大大小。这使它成为可能，尽管仍然不实用。

假设左边的尺寸是n。对于出现的长度为 1 的每个可能组合，您都需要一个状态，即O(2^n). 祝你好运为此写一个正则表达式。您可能最终会有效地枚举大多数可能的组合，并且很少使用实际的状态机逻辑。

状态机示例n=4：注意超过 16 个状态，这只是左侧。这里的每个“接受”状态都需要更复杂的逻辑来匹配右侧。