Issue #9695 has been updated by Yui NARUSE.

Status changed from Open to Rejected

The algorithm is Sunday's quick search, which is a variation of BM, whose cost is O(m*n) as nobu said.

The benchmark happens the worst case for BM variants.

----------------------------------------
Bug #9695: Substring search exhibit quadratic behaviour.
https://bugs.ruby-lang.org/issues/9695#change-46086

* Author: Linus Sellberg
* Status: Rejected
* Priority: Normal
* Assignee: 
* Category: core
* Target version: 
* ruby -v: ruby 2.0.0p247 (2013-06-27 revision 41674) [x86_64-linux]
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN
----------------------------------------
http://nelhagedebugsshit.tumblr.com/post/81301884746/surveying-various-languages-string-search-algorithms

~~~ruby
12.upto(21).map do |i|
  needle='a'*(2**(i-1)) + 'b'
  haystack = 'a' * (2**i)
  a = Time.now; haystack.include?(needle); b=Time.now
  t = b-a
  p [t, t/haystack.length**2]
end
~~~

gives

~~~
[0.000237363, 1.4147937297821046e-11]
[0.000851294, 1.2685269117355347e-11]
[0.003081808, 1.1480629444122315e-11]
[0.013984239, 1.3023837469518185e-11]
[0.035659327, 8.302584057673811e-12]
[0.136899401, 7.968593912664801e-12]
[0.545703233, 7.941027186461724e-12]
[2.217092242, 8.065734589763452e-12]
[8.965134534, 8.15374235935451e-12]
[36.113581501, 8.211277759301083e-12]
=> 
~~~

Wasn't me that found it but it seems the founder hasn't reported it yet. 




-- 
https://bugs.ruby-lang.org/