Как разбить последовательность на подпоследовательность?

Question

Предположим, у меня есть последовательность целых чисел, и мне нужно разделить ее на подпоследовательность, подобную этой:

def splitBySeq(xs: Seq[Int], ys: Seq[Int]): (Seq[Int], Seq[Int]) = ???

val xs = List(1, 2, 3, 4, 5)
splitBySeq(xs, Nil)                 // (List(1, 2, 3, 4, 5), Nil)
splitBySeq(xs, List(1))             // (Nil, List(2, 3, 4, 5))
splitBySeq(xs, List(5))             // (List(1, 2, 3, 4), Nil)
splitBySeq(xs, List(3, 4))          // (List(1, 2), List(5))
splitBySeq(xs, List(11, 12))        // (List(1, 2, 3, 4, 5), Nil)
splitBySeq(xs, List(1, 2, 3, 4, 5)) // (Nil, Nil)

Если ys является подпоследовательностью xs, то функция должна вернуть пару последовательностей - xs1 и xs2, так что xs1 ++ ys ++ xs2 == xs. В противном случае функция возвращает xs.

Как бы вы реализовали splitBySeq?

Answer 1

Это похоже на то, что вы ищете.

def splitBySeq(xs: Seq[Int], ys: Seq[Int]): (Seq[Int], Seq[Int]) = {
  val idx = xs indexOfSlice ys
  if (idx < 0) (xs, Nil)
  else {
    val (a,b) = xs splitAt idx
    (a, b drop ys.length)
  }
}

Обратите внимание, что в 1-м тестовом примере, splitBySeq(xs, Nil), результаты seqs переключаются, потому что Nil соответствует нулевому индексу любого Seq.

Answer 2

Другое решение с хвостовой рекурсивной функцией, выполняющей одну итерацию:

def splitBySeq[A](xs: Seq[A], ys: Seq[A]): (Seq[A], Seq[A]) = {

  @tailrec
  def go(a: List[A], b: List[A], acc: List[A], rest: List[A]): (Seq[A], Seq[A]) = {

    (a, b) match {
      case (z :: zs, w :: ws)  => {
        if(z == w) {
          go(zs, ws, z :: acc, rest)
        } else{
          go(zs, ys.toList, Nil, z :: (acc ++ rest))
        }
      }
      case (zs, Nil) => (rest.reverse, zs)
      case (Nil, _) => (rest.reverse, Nil)
    }
  }

  if(ys.isEmpty) {
    (xs, Nil)
  } else {
    go(xs.toList, ys.toList, Nil, Nil)
  }

}