C11STR2 – spoj

Đề bài:

Thuật toán:

  • Nhận thấy nếu $x$ ký tự cuối của xâu $a$ trùng với $x$ ký tự cuối của xâu $b$ thì có thể ghép. Để kiểm tra hai xâu con có trùng nhau không với ĐPT O(n) thì ta sử dụng Hash.
  • Ta cần tìm $x$ lớn nhất.
  • Ta sẽ duyệt $x$ từ max(length(a),length(b)) về 0. Nếu đã tìm thấy $x$ thỏa mãn thì break.

Code:

{$H+}
uses math;
const
  fi='';
  fo='';
  base=trunc(1e9);
  pp=307;
  maxn=trunc(1e5);
var
  a,b,c : string;
  i,j,n,m : longint;
  ha,hb : array[0..maxn] of int64;
  pow : array[0..maxn] of int64;
procedure enter;
begin
  assign(input,fi);reset(input);
  readln(a);
  readln(b);
  close(input);
end;
procedure swap( var m,n : longint; var a,b : string);
var tg1 : longint;
    tg2 : string;
begin
  tg1 := m ; m := n ; n:= tg1;
  tg2 := a; a :=b ; b:= tg2;
end;
function getha(l,r : longint) : int64;
  begin
    getha := (ha[r]-ha[l-1]*pow[r-l+1] + base*base)  mod base;
  end;
function gethb(l,r : longint) : int64;
  begin
    gethb := (hb[r]-hb[l-1]*pow[r-l+1] + base*base) mod base;
  end;
procedure process;
begin
  m := length(a); n := length(b);
  c := a + b;
  //if m<n then swap(m,n,a,b);
  pow[0] := 1;
  for i:=1 to max(m,n) do pow[i] := pow[i-1]*pp mod base;
  ha[0] := 0; hb[0] := 0;
  for i:=1 to m do ha[i] := (ha[i-1]*pp + ord(a[i])-48) mod base;
  for i:=1 to n do hb[i] := (hb[i-1]*pp + ord(b[i])-48) mod base;
  for i:=min(m,n) downto 1 do
    if gethb(1,i) = getha(m-i+1,m) then
      begin
        delete(c,m-i+1,i);
        break;
      end;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(c);
  close(output);
end;
begin
  enter;
  process;
  print;
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*