MSTRING - String problem
Tác giả: ll931110
Ngôn ngữ: Pascal
{$H+} //String's length is greater than 255
program toki;
const
input = '';
output = '';
maxn = 1000;
var
s,t: string;
F: array[1..maxn,1..maxn] of longint;
pos: array['a'..'z',0..maxn] of longint;
num: array['a'..'z'] of longint;
res: longint;
procedure init;
var
fi: text;
begin
assign(fi,input);
reset(fi);
readln(fi, s); readln(fi, t);
close(fi);
end;
procedure enter;
var
i: longint;
begin
fillchar(pos, sizeof(pos), 0);
fillchar(num, sizeof(num), 0);
for i := 1 to length(t) do
begin
inc(num[t[i]]);
pos[t[i],num[t[i]]] := i;
end;
end;
procedure dp;
var
n,i,j,tmp: longint;
inf,sup,med: longint;
max: longint;
begin
fillchar(F, sizeof(F), 0);
n := length(s);
for i := 1 to n do
begin
F[1,i] := pos[s[i],1];
if F[1,i] = 0 then
begin
res := 1;
exit;
end;
end;
i := 1;
repeat
inc(i);
max := F[i - 1,i - 1];
for j := i to n do
begin
if pos[s[j],num[s[j]]] <= max then
begin
res := i;
exit;
end;
inf := 1;
sup := num[s[j]];
repeat
med := (inf + sup) div 2;
if pos[s[j],med] <= max then inf := med + 1 else
begin
tmp := med;
sup := med - 1;
end;
until inf > sup;
F[i,j] := pos[s[j],tmp];
if max < F[i - 1,j] then max := F[i - 1,j];
end;
until false;
end;
procedure printresult;
var
fo: text;
begin
assign(fo, output);
rewrite(fo);
writeln(fo, res);
close(fo);
end;
begin
init;
enter;
dp;
printresult;
end.