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.

Download