对于仅支持+
, ?
, *
, .
, |
, [..]
, [^..]
, ^
, $
,的正则表达式(..)
,可以匹配递归:{<some-regex-name>}
使用 lengthm
和字符串 length n
。
(正则表达式不支持正/负前瞻/后视)
匹配器的最佳复杂度是多少?
例子:
支架匹配:
brackets = (\({brackets}\))*
// brackets can match:
// ((()())())()
一些随机的“双重”递归:
a = \(({a}|{b})?\)
b = \[{a}(,{b})*\]
// a can match:
// (([(),[(),[()]][(())]]))
没有空格的 Json:
string = "([^\\"]|\\.)"
object = \{ ( {string}:{value}(,{string}:{value})* )? \}
number = [0-9]+(\.[0-9]*)?
list = \[({value}(,{value})*)?]
value = object|string|number|list|true|false
// value can match:
// {"key":false,"ab\"c":[false,12.3,[{}]]}
我有一个想法如何以复杂的方式实现这一点,字符串的大小在O(m^2*n^3)
哪里,正则表达式的大小在哪里。我还没有实现这个,所以也许我有一个错误n
m