package lcs

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"strings"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/10 02:17
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description
 **/
type LCS_Dynamic struct {
	matrixCount [][]int
}

func (m *LCS_Dynamic) LcsStrMethod(source, pattern string) string {
	m.lcsOperation(source, pattern)
	sourceArr := source[0:]
	raw := len(m.matrixCount)
	column := len(m.matrixCount[0])
	sb := strings.Builder{}
	i, j := raw-1, column-1
	for i >= 1 && j >= 1 {
		if m.matrixCount[i][j] == m.matrixCount[i-1][j-1]+1 { // tips : 字符串匹配关系
			sb.WriteString(string(sourceArr[i-1])) // attention : 此处矩阵和匹配字符串之间的关系是 i-1
			i--
			j--
		} else if m.matrixCount[i][j] == m.matrixCount[i-1][j] {
			i--
		} else {
			j--
		}
	}
	// grammar字符串反转的方式
	ans := sb.String()
	ansArr := []rune(ans)
	for k := 0; k < len(ansArr)/2; k++ {
		ansArr[k], ansArr[len(ans)-1-k] = ansArr[len(ans)-1-k], ansArr[k]
	}
	return string(ansArr)
}

func (m *LCS_Dynamic) LcsCountMethod(source, pattern string) int {
	return m.lcsOperation(source, pattern)
}

func (m *LCS_Dynamic) lcsOperation(source, pattern string) int {
	if len(source) == 0 || len(pattern) == 0 {
		return 0
	}
	sourceArr := source[0:]
	patternArr := pattern[0:]
	m.matrixCount = make([][]int, len(sourceArr)+1, len(patternArr)+1)
	for i := 0; i <= len(sourceArr); i++ {
		m.matrixCount[i] = make([]int, len(patternArr)+1, len(patternArr)+1)
	}
	for i := 1; i <= len(sourceArr); i++ {
		for j := 1; j <= len(patternArr); j++ {
			if sourceArr[i-1] == patternArr[j-1] {
				m.matrixCount[i][j] = m.matrixCount[i-1][j-1] + 1
			} else {
				if m.matrixCount[i-1][j] > m.matrixCount[i][j-1] {
					m.matrixCount[i][j] = m.matrixCount[i-1][j]
				} else {
					m.matrixCount[i][j] = m.matrixCount[i][j-1]
				}
			}
		}
	}
	return m.matrixCount[len(sourceArr)][len(patternArr)]
}

func (m *LCS_Dynamic) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.LCS, C.Dynamic},
		Desc: &C.Desc{
			Name:   "LCS_Dynamic",
			NameCn: "最长公共子序列:动态规划",
			ParamsDesc: map[string]string{
			},
			Example: map[int]string{
			},
		},
	}
}