Project

General

Profile

Actions

Bug #19467

closed

Some linear_time regexp does not match in linear time

Added by tompng (tomoya ishida) over 1 year ago. Updated over 1 year ago.

Status:
Closed
Target version:
-
ruby -v:
ruby 3.3.0dev (2023-02-17T18:10:16Z master c3bae033eb) [x86_64-linux]
[ruby-core:112594]

Description

Regexp.linear_time?(/\A.*a.*x\z/) #=> true but it does not match in linear time

Regexp.linear_time? /\A(.*a.*)x\z/ #=> true
/\A(.*a.*)x\z/ =~ 'a'*100000+'y' #=> nil, processing time: 0.016995s

Regexp.linear_time? /\A.*a.*x\z/ #=> true
/\A.*a.*x\z/ =~ 'a'*100000+'y' #=> nil, processing time: 21.479335s
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0