algorithm – 一种有效的技术,用于替换具有可变或不可变状态的序

这样做的一种方法是：

def myReplace(input: List[Op],pattern: List[Op],replacement: List[Op]) = {
  // This function should be part of an KMP algorithm instead,for performance
  def compare(pattern: List[Op],list: List[Op]): Boolean = (pattern,list) match {
    case (x :: xs,y :: ys) if x == y => compare(xs,ys)
    case (Nil,Nil)                   => true
    case _                            => false
  }

  var processed: List[Op] = Nil
  var unprocessed: List[Op] = input
  val patternLength = pattern.length
  val reversedReplacement = replacement.reverse

  // Do this until we finish processing the whole sequence
  while (unprocessed.nonEmpty) {

    // This inside algorithm would be better if replaced by KMP

    // Quickly process non-matching sequences
    while (unprocessed.nonEmpty && unprocessed.head != pattern.head) {
      processed ::= unprocessed.head
      unprocessed = unprocessed.tail
    }

    if (unprocessed.nonEmpty) {
      if (compare(pattern,unprocessed)) {
        processed :::= reversedReplacement
        unprocessed = unprocessed drop patternLength
      } else {
      processed ::= unprocessed.head
      unprocessed = unprocessed.tail
      }          
    }
  }

  processed.reverse
}

您可以通过使用KMP获得速度,特别是如果搜索的模式很长.

现在,这个算法有什么问题？问题是它不会测试被替换的模式是否在该位置之前引起匹配.例如,如果我用C替换ACB,并且我有一个输入AACBB,那么这个算法的结果将是ACB而不是C.

要避免此问题,您应该创建一个回溯.首先,检查模式中的哪个位置可能发生替换：

val positionOfReplacement = pattern.indexOfSlice(replacement)

然后,您修改算法的替换部分：

if (compare(pattern,unprocessed)) {
        if (positionOfReplacement > 0) {
          unprocessed :::= replacement
          unprocessed :::= processed take positionOfReplacement
          processed = processed drop positionOfReplacement 
        } else {
          processed :::= reversedReplacement
          unprocessed = unprocessed drop patternLength
        }
      } else {

这将足够回溯以解决问题.

然而,这个算法不能有效地处理多个模式,我猜你就是这样.为此,您可能需要对KMP进行一些调整,以便有效地进行,或者使用DFA来控制可能的匹配.如果你想匹配AB和ABC,情况会更糟.

在实践中,完全打击问题相当于正则表达式匹配&替换,替换是匹配的函数.当然,这意味着您可能需要开始研究正则表达式算法.

编辑

我忘了完成我的推理.如果该技术由于某种原因不起作用,那么我的建议是使用不可变的基于树的向量.基于树的矢量使得能够以低复制量替换部分序列.

如果不这样做,那么解决方案就是双重链接列表.从一个带有切片替换的库中选择一个 – 否则你最终可能花费太多时间来调试已知但棘手的算法.