我正在尝试提出一个 GNU 扩展正则表达式来检测一串 ascii 编码位中的重复子字符串。我有一个有效的表达方式——有点。问题是当给定一个可能有很多解决方案的字符串时，它的执行速度非常慢
表达方式
([01]+)(\1)+
编译速度很快，但对字符串执行大约需要一分钟
1010101010101010101010101010101010101010101010101010101010
我正在使用 glibc 2.5-49 中的正则表达式实现（CentOS 5.5 附带。）
FWIW，pcre 库执行得很快，就像直接在 gregexp 或 perl 中一样。所以显而易见但错误的答案是“使用 libpcre”。我不能轻易地在我的项目中引入新的依赖项。我需要在 CentOS/RHEL 附带的标准 C 库中工作。
如果输入字符串可以是任何相当长的长度，或者如果性能完全是一个问题，那么解决这个问题的更好方法之一不是使用正则表达式，而是使用更复杂的字符串数据结构来促进这些类型的查询更有效率。
这样的数据结构就是后缀树。给定一个 string S，它的后缀树本质上是它所有后缀的Patricia trie。尽管它看起来很复杂，但它可以在线性时间内构建。
后缀树
"BANANA"（由维基百科提供）
您可以使用后缀树真正有效地执行多种查询，例如查找子字符串的所有出现、至少出现两次的最长子字符串等。您所追求的字符串类型称为串联重复。为了促进此查询，您必须在线性时间内预处理后缀树，以便您可以在恒定时间内执行最低公共祖先查询。
这个问题在计算生物学中非常常见，其中 DNA 可以被视为一个非常长的字符串，由ACGT. 因此，性能和效率至关重要，因此设计了这些非常复杂的算法和技术。
您应该考虑从头开始为您的二进制序列实施这些技术，或者将您的二进制序列映射到“假”DNA 字符串然后使用可用于基因研究的众多工具之一更容易。