千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2020年8月実施 専門 A5

标签：

• Longest-Common-Subsequence

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

次の Pascal プログラムについて答えよ。

program test(input, output);
const N = 4;
var s1, s2: packed array[1..N] of char;
    t: array[0..N,0..N] of integer;
    i,j: integer;
begin
  s1 := 'abca'; s2 := 'bcba';
  for j := 0 to N do t[0,j] := 0;
  for i := 1 to N do t[i,0] := 0;
  for i := 1 to N do
    for j := 1 to N do
      if s1[i] = s2[j] then t[i,j] := t[i-1,j-1]+1
      else if t[i-1,j] > t[i,j-1] then t[i,j] := t[i-1,j]
      else t[i,j] := t[i,j-1];
  writeln(t[N,N])
end.

1. 出力時点の配列 $t$ の内容を記せ。
2. $N$ を一般の正整数とし、$s1,s2$ に任意の長さ $N$ の文字列を代入した場合、出力が何を表すか理由とともに述べよ。

题目描述

对上面的 Pascal 程序：(1) 写出输出时数组 $t$ 的全部元素；(2) 将 $N$ 推广为任意正整数，且输入任意两个长度为 $N$ 的字符串，解释输出的含义并证明。

Kai

(1) 行を $i=0,\ldots,4$、列を $j=0,\ldots,4$ の順に並べると

$$t=\begin{pmatrix} 0&0&0&0&0\\ 0&0&0&0&1\\ 0&1&1&1&1\\ 0&1&2&2&2\\ 0&1&2&2&3 \end{pmatrix}.$$

出力は $3$ である。

(2) $t[i,j]$ は $s1$ の先頭 $i$ 文字と $s2$ の先頭 $j$ 文字の最長共通部分列の長さである。空文字列との長さは $0$。末尾が異なる場合、共通部分列は少なくとも一方の末尾を使わないため、最適値は $\max(t[i-1,j],t[i,j-1])$ となる。末尾が同じ文字なら、その文字を両方の最後に用いる最長共通部分列を選べるので、最適値は $t[i-1,j-1]+1$ である。従って添字和に関する帰納法から主張が成り立ち、出力は二文字列全体の最長共通部分列長となる。