Playing with Diff

diff.R

diff_rdiff <- function(target, current) {
  stopifnot(is.character(target), is.character(current))
  a <- tempfile("unitizerRdiffa")
  writeLines(target, a)
  b <- tempfile("unitizerRdiffb")
  writeLines(current, b)
  diff <- capture.output(system(paste("diff -bw", shQuote(a), shQuote(b))))
}

differ <- function(A, B) {
  N <- length(A)
  M <- length(B)
  MAX <- M + N
  OFF <- MAX + 1L  # offset to adjust to R indexing
  Vl <- vector("list", MAX)
  for(D in seq(0L, MAX)) {
    V <- integer(2L * MAX + 1L)
    for(k in seq(-D, D, by=2L)) {
      # not sure of precendence for || vs &&
      # k == -D means x == 0
      if(k == -D || (k != D && V[k - 1L + OFF] < V[k + 1L + OFF])) {
        x <- V[k + 1L + OFF]
      } else {
        x <- V[k - 1L + OFF] + 1L
      }
      y <- x - k
      
      # Move on diagonal
      while (x < N && y < M && A[x + 1L] == B[y + 1L]) {
        x <- x + 1L
        y <- y + 1L
      }  
      V[k + OFF] <- x
      if(x + 1L >= N && y + 1L >= M) {
        # Determine backtrack path looking for closes diagonal by
        res <- matrix(integer(1L), nrow=D + 1L, ncol=2)
        res[D + 1L, ] <- c(x, y)
        
        for(d in seq(D-1L, 0L)) {
          broke <- FALSE
          for(i in seq(d, 0L)) {
            # Check vertical and horizontal branches to see if there is a
            # snake by adding/subtracting i
            
            Vp <- Vl[[d]]
            if(Vp[k + i + OFF] == x + i - 1L) {
              res[d, ] <- c(x + i - 1L, x + i - 1L - (k + i))
              broke <- TRUE
              break
            } else if(i && Vp[k - i + OFF] == x - i - 1L) {
              res[d, ] <- c(x - i - 1L, x - i - 1L - (k - i))
              break
              broke <- TRUE
            }
          }
          if(!broke) stop("Logic Error, should never get here")
        }
      }
      return(res)
    }
  }
}

GARB <- do.call("paste0", expand.grid(LETTERS, LETTERS, LETTERS))

mb <- readLines("R/random/mobydickch3.txt")
MB <- unlist(strsplit(mb, " "))
A <- B <- MB
B[sample(seq_along(B), 200)] <- sample(GARB, 200)
B <- tail(head(B, -50), -50)


differ(letters[1:3], letters[1:3])

Myers Algo