Хорошо, некоторые соображения должны быть сделаны. Во-первых, напомним, что в списках tail не создает объекты, а предоплата (::) создает только один объект для каждого предварительно добавленного элемента. Вообще говоря, это почти так же хорошо, как вы можете получить.
Один из способов сделать это будет следующим:
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, особенно если искомый шаблон длинный.
Теперь, в чем проблема с этим алгоритмом? Проблема в том, что он не будет проверять, вызывает ли замененный шаблон совпадение перед этой позицией. Например, если я заменю ACB на C, и у меня будет входной 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.
На практике проблема полного удара эквивалентна сопоставлению и замене регулярного выражения, где замена является функцией совпадения. Это означает, что, конечно, вы можете начать изучать алгоритмы регулярных выражений.
EDIT
Я забыл закончить свои рассуждения. Если по какой-то причине этот метод не работает, то мой совет - использовать неизменный древовидный вектор. Древовидные векторы позволяют заменять частичные последовательности небольшим количеством копий.
А если это не сработает, то решение состоит из двусвязных списков. И выберите один из библиотеки с заменой фрагмента - в противном случае вы можете потратить слишком много времени на отладку известного, но сложного алгоритма.