C11STR2 – spoj

Đề bài:

• http://vn.spoj.com/problems/C11STR2/

Thuật toán:

• Nhận thấy nếu [latex]x[/latex] ký tự cuối của xâu [latex]a[/latex] trùng với [latex]x[/latex] ký tự cuối của xâu [latex]b[/latex] 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 [latex]x[/latex] lớn nhất.
• Ta sẽ duyệt [latex]x[/latex] từ max(length(a),length(b)) về 0. Nếu đã tìm thấy [latex]x[/latex] thỏa mãn thì break.

Code:

• Pascal (xem)

{$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