[学習記録]AtCoder EDP F-LCS

問題

問題文

文字列 s および t が与えられます。 s の部分列かつ t の部分列であるような文字列のうち、最長のものをひとつ求めてください。

制約

• s および t は英小文字からなる文字列である。

• 1≤∣s∣,∣t∣≤3000

解法

s, tを１文字ずつ取り出し、処理を行う。dpには最大文字数を記録する。

• マッチした　　→　１文字前の最大長　＋　１（マッチした文字）

• マッチしない　→　１文字前の最大長(s) と　１文字前の最大長(t)の最大

for i := 1; i <= s_len; i++ {
	dp[i] = make([]int, t_len+1)
	s := s_sli[i-1]

	for j := 1; j <= t_len; j++ {
		t := t_sli[j-1]
		if s == t {
			dp[i][j] = dp[i-1][j-1] + 1
		} else {
			dp[i][j] = Max(dp[i-1][j], dp[i][j-1])
		}
	}
}

dpができたら、ここから文字列を復元する必要がある。復元したら、その配列を１文字ずつ出力したものが回答になる。

// 最大文字数を取得し、それを格納するスライスを作る
len := dp[s_len][t_len]
ans := make([]string, len)

for i, j := s_len, t_len; len > 0; {
	if s_sli[i-1] == t_sli[j-1] {
        // 文字が同じ場合はそれを出力用に保持（len 文字目）
		ans[len-1] = s_sli[i-1]

        // s, t ともにその文字を使うことはできないので、マイナス
		i--
		j--
		len--
	} else if dp[i-1][j] == dp[i][j]-1 {
　　　　 // 文字が違う = どちらかの文字は使わない => dpの値を確認
　　　　 // dp[i-1][j]が減る = dp[i][j-1]の値は同じ => j をマイナス
　　　　 // （dpの値はマッチした時のみ +1されており、それ以外はないため）
		j--
	} else {
		i--
	}
}

for _, v := range ans {
	fmt.Print(v)
}
fmt.Println()

// 参考
//   a b r a c a d a b r a
// a 1 1 1 1 1 1 1 1 1 1 1
// v 1 1 1 1 1 1 1 1 1 1 1
// a 1 1 1 2 2 2 2 2 2 2 2
// d 1 1 1 2 2 2 3 3 3 3 3
// a 1 1 1 2 2 3 3 3 3 3 3
// k 1 1 1 2 2 3 3 3 3 3 3
// e 1 1 1 2 2 3 3 3 3 3 3
// d 1 1 1 2 2 3 4 4 4 4 4
// a 1 1 1 2 2 3 4 5 5 5 5
// v 1 1 1 2 2 3 4 5 5 5 5
// r 1 1 2 2 2 3 4 5 5 6 6
// a 1 1 2 3 3 3 4 5 6 6 7
//   a b r a c a d a b r a

コード（AC)

func run() {
	s_sli := strings.Split(read(), "")
	t_sli := strings.Split(read(), "")

	dp := make([][]int, len(s_sli)+1)
	s_len := len(s_sli)
	t_len := len(t_sli)
	dp[0] = make([]int, t_len+1)

	for i := 1; i <= s_len; i++ {
		dp[i] = make([]int, t_len+1)
		s := s_sli[i-1]

		for j := 1; j <= t_len; j++ {
			t := t_sli[j-1]
			if s == t {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = Max(dp[i-1][j], dp[i][j-1])
			}
		}
	}

	len := dp[s_len][t_len]
	ans := make([]string, len)
	for i, j := s_len, t_len; len > 0; {
		if s_sli[i-1] == t_sli[j-1] {
			ans[len-1] = s_sli[i-1]
			i--
			j--
			len--
		} else if dp[i-1][j] == dp[i][j]-1 {
			j--
		} else {
			i--
		}
	}

	for _, v := range ans {
		fmt.Print(v)
	}
	fmt.Println()
}