ThreeStones https://blog.hatena.ne.jp/ThreeStones/ ThreeStonesのアレ https://threestones.hateblo.jp/ 読書 問題概要 ２つの文字列t, sが与えられる。 これら２つの共通部分文字列の長さの最大値を求めよ。 共通部分文字列とは、互いに共有する文字列であり、連続で一致している必要は無いが、 順序は等しくなければならない。 例示 s = "abcd" t = "becd"LCS = 3 (以後LCS(Longest Common Subsequence)は、最長共通部分長を指す) 問題解法 ・動的計画法 漸化式を作る。 (1)i番目とj番目が等しいとき 文字列探索において、tのi番目とsのj番目が等しいとき、 LCS(t(i-1),s(j-1))に1をプラスすればよい。例： t = ABCDEA s = … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fthreestones.hateblo.jp%2Fentry%2F2014%2F06%2F29%2F235343" title="動的計画法part3(最長共通部分列問題) - ThreeStonesのアレ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-06-29 23:53:43 rich https://threestones.hateblo.jp/entry/2014/06/29/235343 1.0 100%