最长公共子序列 Tyvj P1050 Pascal程序,描述 Description一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串.如A=“cdaad",顺次选1,3,5个字符就构成子串"cad",现给定两个字符串,求它们的最长
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/19 11:02:04
最长公共子序列 Tyvj P1050 Pascal程序,描述 Description一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串.如A=“cdaad",顺次选1,3,5个字符就构成子串"cad",现给定两个字符串,求它们的最长
最长公共子序列 Tyvj P1050 Pascal程序,
描述 Description
一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串.如A=“cdaad",顺次选1,3,5个字符就构成子串"cad",现给定两个字符串,求它们的最长共公子串.
输入格式 InputFormat
第一行两个字符串用空格分开.
输出格式 OutputFormat
最长子串的长度.
样例输入 SampleInput [复制数据]
abccd aecd
样例输出 SampleOutput [复制数据]
3
数据范围和注释 Hint
两个串的长度均小于2000
最长公共子序列 Tyvj P1050 Pascal程序,描述 Description一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串.如A=“cdaad",顺次选1,3,5个字符就构成子串"cad",现给定两个字符串,求它们的最长
01
var
02
i,j,k,m,n,s,t:longint;
03
lcs:array[0..2000,0..2000] of longint;
04
x,y:array[0..2000] of char;
05
begin
06
i:=0;
07
repeat
08
inc(i);
09
read(x[i]);
10
until x[i]=' ';
11
n:=i-1;
12
i:=0;
13
while not eoln do
14
begin
15
inc(i);
16
read(y[i]);
17
end;
18
m:=i;
19
for i:=1 to n do
20
for j:=1 to m do
21
begin
22
if x[i]=y[j] then lcs[i,j]:=lcs[i-1,j-1]+1
23
else if lcs[i-1,j]>lcs[i,j-1] then lcs[i,j]:=lcs[i-1,j]
24
else lcs[i,j]:=lcs[i,j-1];
25
end;
26
writeln(lcs[n,m]);
27
end.