记录一下最长公共子串的golang实现

由于最长公共子序列可以使用动态规划使用类似的方式来实现,这里就不做过多的阐述.

子序列和子串的区别就在于连续性的区别,前者可以离散,后者连续.

1. 由于动态规划都需要实现一个生成table的函数,然后根据所得到的table去反向求得子串,依照这个思路就有了下面的代码:

// returns the longest length
func Lcs2(a, b []int) (int, [][]int, int, int) {
	// 1. 根据 a, b生成s表
	lenA, lenB := len(a), len(b)
	s := TwoDimSlice(lenA+1, lenB+1)
	res := 0
	indexI := 0
	indexJ := 0
	for i := 0; i < lenA+1; i++ {
		for j := 0; j < lenB+1; j++ {
			if i == 0 || j == 0 {
				s[i][j] = 0
				continue
			}
			if a[i-1] != b[j-1] {
				s[i][j] = 0
				continue
			}
			if a[i-1] == b[j-1] {
				s[i][j] = s[i-1][j-1] + 1
				//res = max(res, s[i][j])
				if s[i][j] > res {
					res = s[i][j]
					indexI = i
					indexJ = j
				}
				continue
			}
		}
	}
	return res, s, indexI, indexJ
}

//创建一个尺寸为a , b的二维切片
func TwoDimSlice(a, b int) [][]int {
	slice1 := make([][]int, a)
	for i, _ := range slice1 {
		//tmp := make([]int, b)
		//sliceItem = append(sliceItem, tmp...)
		slice1[i] = make([]int, b)
	}
	return slice1
}

// 根据所记录的最大长度的index 来返回最长的子串
func findStr(indexi int, target []int, longest int) string {
	res := ""
	for i := indexi - longest; i < + indexi; i++ {
		res += strconv.Itoa(target[i])
	}

	return res
}

//这就是主要的三个函数 lcs2返回依次是 最长长度, s表, 最大值的横坐标, 最大值的纵坐标
// TwoDimSlice用来构造一个二维切片
// 第三个是用来查找相同的子串