package main

import (
	"fmt"
)

func main() {
	left := []string{`a`,`b`,`d`,`e`,`f`,`g`,`i`,`j`,`k`}
	right := []string{`b`,`c`,`d`,`e`,`h`,`i`,`j`,`k`}

	res := merge(left, right)

	fmt.Println(res)
}


// merge merges left array to right
func merge(left, right []string) []string {
	rightIdx := toMap(right)

	out := make([]string, len(right))
	copy(out, right)

	lastFoundIdx := -1
	insertedElementsLen := 0

	for k, v := range left {
		if pos, ok := rightIdx[v]; ok {
			// Real position should be increased by length of inserted elements
			pos += insertedElementsLen

			newElementsFromLeft := make([]string, len(left[lastFoundIdx+1:k]))
			copy(newElementsFromLeft, left[lastFoundIdx+1:k])

			out = append(out[:pos], append(newElementsFromLeft, out[pos:]...)...)
			insertedElementsLen += len(newElementsFromLeft)
			lastFoundIdx = k
		}
	}

	// Insert rest elements after last found index
	if lastFoundIdx < len(left) {
		if lastFoundIdx == -1 {
			out = append(out, left...)
		} else {
			pos := rightIdx[left[lastFoundIdx]] + insertedElementsLen
			out = append(out[:pos+1], append(left[lastFoundIdx+1:], out[pos+1:]...)...)
		}
	}

	// Drop local deleted elements from out

	return out
}

func toMap(arr []string) map[string]int {
	out := map[string]int{}

	for i, value := range arr {
		out[value] = i
	}

	return out
}