小编sir*_*usa的帖子

我需要在String中找到最长的非重叠重复子字符串.我有可用字符串的后缀树和后缀数组.

当允许重叠时,答案是微不足道的(后缀树中最深的父节点).

例如对于String ="acaca"

如果允许重叠,则回答是"aca"但是当不允许重叠时,回答是"ac"或"ca".

我只需要算法或高级想法.

PS:我试过,但我在网上找不到明确的答案.

我正在尝试基于探索Ruby的正则表达式算法中概述的回溯方法来实现正则表达式匹配器。编译后的正则表达式将转换为虚拟机命令数组；为了回溯，当前命令和输入字符串索引以及捕获组信息保留在堆栈中。

在“ 正则表达式匹配：虚拟机方法 Cox”中提供了有关如何将某些正则表达式组件编译为VM命令的更多详细信息，尽管所讨论的实现有所不同。根据这些文章，我的实现对于标准分组，字符类和重复组件非常有效。

现在，我想看看这种实现有哪些扩展和优化选项。Cox在他的文章中提供了许多有关DFA / NFA方法的有用信息，但是有关回溯方法的扩展或优化技术的信息却很少。

例如，关于他提到的反向引用

回溯在回溯实现中很简单。

并给出了DFA方法的想法。但是对我来说，尚不清楚如何通过VM方法“轻松地”完成。到达backreference命令后，您必须将来自相应组的先前匹配的字符串编译到另一组VM命令中，并以某种方式将这些命令合并到当前VM中，或者维护第二个VM并暂时将执行切换到该VM。

他还提到了通过使用超前方式在重复中可能进行的优化，但是没有详细说明如何实现。在我看来，这可以用来减少回溯堆栈上的项目数量。

tl; dr针对基于VM的回溯正则表达式实现存在哪些常规优化技术，它们如何工作？请注意，我并不是在寻找特定于某种编程语言的优化，而是在寻找这种正则表达式实现的通用技术。

编辑：如第一个链接中所述，Oniguruma库正是使用基于堆栈的回溯方法来实现正则表达式匹配器。也许有人可以解释该库所做的优化，这些优化可以推广到其他实现中。不幸的是，该库似乎未提供有关源代码的任何文档，并且该代码也缺少注释。

编辑2：在阅读有关解析表达语法（PEG）的文章时，我偶然发现了一篇关于Lua PEG实现的论文，该论文利用了类似的基于VM的方法。本文提到了一些优化选项，以减少已执行的VM命令的数量以及回溯堆栈的不必要增长。

我目前正在尝试将部分Windows API移植到Haskell.其中一个功能是SetConsoleCtrlHandler注册一个处理程序回调,只要从控制台输入接收到Ctrl + C或Ctrl + Break,就会调用它.所以这里有一个小样本程序:

{-# LANGUAGE CPP #-}
{-# LANGUAGE ForeignFunctionInterface #-}
module Main where

import Control.Monad
import GHC.ConsoleHandler
import Foreign
import System.Win32.Process
import System.Win32.Types

foreign import ccall "wrapper"
    makeHandlerPtr :: (DWORD -> IO BOOL) -> IO (FunPtr (DWORD -> IO BOOL))

foreign import stdcall "windows.h SetConsoleCtrlHandler"
    c_SetConsoleCtrlHandler :: FunPtr (DWORD -> IO BOOL) -> BOOL -> IO BOOL

main :: IO ()
main = unsafeCtrl

unsafeCtrl :: IO ()
unsafeCtrl = do
    ptrHandler <- makeHandlerPtr …

我正在寻找一个像Data.Map使用区间作为键的Haskell容器类型,其中最左侧和最右侧的键也可以是无界区间,但在其他方面不重叠.此外,容器应该支持类似于zipWith允许将两个容器合并为一个新容器的函数,使用两个键集的交集作为新键集和两个值集的逐点组合的参数函数.

已有几个包提供基于区间的地图.我看了一下IntervalMap,fingertree和SegmentTree,但这些包装似乎提供所需的组合功能.它们似乎都使用交集函数的间隔,在两个映射中都是相等的,而我需要一个版本,如果需要,可以将间隔分解为较小的间隔.

容器应基本上为表单的键/值系列提供有效且可存储的映射Ord k => k -> Maybe a,即仅在特定间隔上定义的函数或具有映射到相同值的较大间隔的函数.

这是一个展示问题的小例子:

... -4 -3 -2 -1  0  1  2  3  4  ...  -- key set
-----------------------------------
... -1 -1 -1 -1  0  1  1  1  1  ...  -- series corresponding to signum
...  5  5  5  5  5  5  5  5  5  ...  -- series corresponding to const 5

第一个系列可以通过映射有效表达,[-infinity, -1] -> -1; [0, 0] -> …

对于已经以拆分格式给出的大量输入数据（例如大量的单个数据库条目），解析器的并行化似乎很容易，或者很容易通过快速的预处理步骤进行拆分（例如，将句子的语法结构解析为大型）文本。

似乎很难进行并行解析，这已经需要付出很多努力才能在给定输入中定位子结构。通用编程语言代码看起来像一个很好的例子。在Haskell之类的使用布局/缩进分隔单个定义的语言中，您可能会在找到新定义的开始后检查每行的前导空格数，跳过所有行，直到找到另一个定义并传递每个定义跳过块到另一个线程进行完全解析。

对于使用平衡括号定义范围的C，JavaScript等语言，进行预处理的工作量会更高。您需要遍历整个输入，从而计算大括号，注意字符串文字中的文本，等等。对于XML之类的语言而言，情况更糟，您还需要在打开/关闭标签中跟踪标签名称。

我发现CYK解析算法的并行版本似乎适用于所有无上下文语法。但是我很好奇还有什么其他通用概念/算法可以使解析器并行化，包括上述大括号计数这样的事情，它们仅适用于有限的一组语言。这个问题不是关于特定的实现，而是关于这些实现的思想。

我正在探索优化基于堆栈的回溯正则表达式实现的方法（另请参见本主题）。在评论中给出了有关Perl的正则表达式匹配器的提示。从源代码中，我已经发现，在将正则表达式与几种替代方案进行匹配时，它会使用尝试。

例如，像/(?:foo|bar|baz|foobar)$/这样的正则表达式通常会产生类似的程序

BRANCH
  EXACT <foo>
BRANCH
  EXACT <bar>
BRANCH
  EXACT <baz>
BRANCH
  EXACT <foobar>
EOL

而使用特里的优化版本看起来像

TRIE-EXACT
  <foo>
  <bar>
  <baz>
  <foobar>
EOL

带有EXACT命令的四个分支分别优化为一个TRIE命令。

但是，对于回溯，我不理解在执行阶段如何使用该Trie。

考虑未优化的代码和输入字符串foobar。当试图匹配正则表达式，第一个分支foo会成功匹配时，$会失败，接下来的树枝bar和baz会失败，最终分支foobar将匹配，$将匹配，并成功匹配完成。

现在，匹配如何与Trie一起工作？根据我的理解，特里只有一种合理的隐含顺序，其中尝试重叠的条目，即最长的匹配优先。在上述示例中，这将给出正确的匹配。

但这会给/(?:foo|foobar)barr$/和输入错误的结果foobarr。特里将匹配foobar，但在下一个失败，r因为它期望b下一个。因此，不仅必须有一种在Trie中回溯的方法，而且还必须以某种方式保留分支的原始顺序，否则优化的程序在语义上将与非优化的版本不同。

Perl实现如何处理这种基于树的匹配？