Bird-Meertens 可以用来计算 Haskell 中最长有效括号问题的线性时间解吗？

Question

问题：给定仅由

(

和

)

字符组成的字符串，计算括号中最长匹配/有效子串的长度。

这是一个简单的解决方案：

isValid :: String -> Bool
isValid = go' (0 :: Int)
  where
    go' = memo2 go
    go 0 [] = True
    go 0 (')' : _ ) = False
    go n (')' : cs) = go' (n-1) cs
    go n ('(' : cs) = go' (n+1) cs
    go _ _ = False

solution :: String -> Int
solution = longest . valid . substrings
  where
    substrings = tails >=> inits
    valid      = filter isValid
    longest    = maximum . map length

现在我发现我可以很容易地想出这些低效、简单的解决方案来解决编程问题，但高效的版本却更加难以捉摸。 Bird-Meertens 形式主义的整个想法是，如果你能想出一个慢速版本，微积分会给你一个快速版本，所以我希望它可能会有一些用处。

此外，这看起来与维基百科上的示例相似，因为我们正在计算所有可能的子数组，映射某些内容，并在最后取最大值。

Bird-Meertens 可以帮助我们吗？

我尝试内联定义并到达这里：

solution = maximum . map length . concat . map (filter isValid . tails) . inits

但对我来说，从这一点开始适用任何相关规则并不明显。

Answer 1

您可以通过移动光标在线性时间内生成它，并进行一些簿记和保留堆栈。

如果遇到左括号，则将该括号的位置（索引）压入堆栈。如果遇到右括号，则从堆栈中弹出，右括号的索引减去从堆栈中弹出的项的索引就是到目前为止的长度。

所以我们可以合作：

solution :: String -> Int
solution = go [] 0
  where go [] i (')':xs) = go [] (i+1) xs
        go (d:ds) i (')':xs) = max (i-d+1) (go ds (i+1) xs)
        go ds i ('(':xs) = go (i:ds) (i+1) xs
        go _ _ [] = 0

因此，我们从一个空列表（我们将用作堆栈）、索引

0

和要处理的字符串开始。

如果我们遇到右括号，并且堆栈为空，我们就继续前进，在这种情况下，字符串在该字符之前都是无效的，因此我们继续寻找有效的子字符串。

如果有右括号并且堆栈不为空，则

d

和

i

（两者都包含）之间的字符串是有效匹配，因此我们将

i-d+1

视为可能的结果，并且我们对其余部分进行递归列表中的。

左括号只是标记了堆栈上的起始索引，如果我们到达字符串的末尾，我们将返回

0

作为该子字符串的答案。