研究人员证明所有最长正则表达式匹配可以在线性时间内完成，解决了正则表达式理论中的一个基本缺陷——即使是RE2、Go和Rust等现代引擎在处理多重匹配时也会破坏其线性时间保证。这一突破对文本编辑器、搜索工具和依赖全面正则匹配的数据处理应用具有重要意义。该研究挑战了长期以来主要关注单匹配问题而忽略实际多匹配需求的学术假设。
背景
正则表达式是编程、搜索和数据提取中基本文本处理工具，但传统实现在高效查找字符串中所有匹配方面存在困难。大多数正则表达式引擎仅保证单匹配的线性时间复杂度，而多匹配操作可能达到二次时间复杂度。
- 来源
- Lobsters
- 发布时间
- 2026年3月17日 19:58
- 评分
- 8.0 / 10