C11STR2 – spoj

July 25, 2017 by Leave a Comment

Đề 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.
Chủ đề: Hashing, SPOJ

PALINY – spoj

January 5, 2017 by Leave a Comment

Đề bài:

Thuật toán:

Chặt nhị phần + Hash

Code:

{$H+}
uses math;
const
  fi='';//paliny.inp';
  fo='';//paliny.out';
  maxn=50003;
  pp=307;
  base=trunc(1e9)+7;
var
  i,j,n,d,c,g,top,ans : longint;
  ha,hb,pow : array[0..maxn] of int64;
  a : array[1..maxn] of longint;
  s : string;
function gethash1(l,r : longint) : int64;
  begin
    gethash1 := (ha[r] - ha[l-1] * pow[r-l+1] + base * base) mod base;
  end;
function gethash2(l,r : longint) : int64;
  begin
    gethash2 := (hb[r] - hb[l+1] * pow[l-r+1] + base * base) mod base;
  end;
function ok ( le : longint) : boolean;
  var i,j : longint;
  begin
    for i := 1 to n - le + 1 do
      if gethash1(i,i+le-1) = gethash2(i+le-1,i) then exit(true);
    exit(false);
  end;
procedure process;
  begin
  d := 1 ;
  c := top ;
  g := (d+c) div 2;
  while (G<>d) and (g<>C) do
    begin
      if ok (a[g]) then d := g else c := g;
      g := (d+c) div 2;
    end;
  for g := c downto d do
    if ok (a[g]) then
      begin
        ans := max(ans,a[g]);
        exit;
      end;
  end;
procedure push(x : longint);
  begin
    inc(top);
    a[top] := x;
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(n);
  readln(s);
  pow[0] := 1;
  for i := 1 to n do pow[i] := pow[i-1] * pp mod base;
  for i := 1 to n do ha[i] := ( ha[i-1] * pp + ord(s[i]) ) mod base;
  for i := n downto 1 do hb[i] := ( hb[i+1] * pp + ord(s[i]) ) mod base;
  top := 0;
  for i := 1 to n do
    if i mod 2 = 0 then push(i);
  process;
  top := 0;
  for i := 1 to n do
    if i mod 2 = 1 then push(i);
  process;
  writeln(ans);
  close(input);close(output);
end.
Chủ đề: Hashing, Tìm kiếm nhị phân

SUBSTR – SPOJ

August 26, 2016 by Leave a Comment

Đề bài: http://yeulaptrinh.de/319/substr-spoj/

Thuật toán:

  • (đang cập nhập)

    • Code:

    const
  fi='';
  fo='';
  maxn=trunc(1e6);
  base=trunc(1e9)+7;
  pp=307;
var
  f : array[0..maxn] of int64;
  i,j,n,m : longint;
  hb : int64;
  a,b : array[1..maxn] of byte;
  ha,pow : array[0..maxn] of int64;
procedure enter;
var x : ansistring;
begin
  assign(input,fi);reset(input);
  readln(x);
  m := length(x);
  for i := 1 to m do a[i] := ord(x[i])-48;
  readln(x);
  n := length(x);
  for i := 1 to n do b[i] := ord(x[i])-48;
  close(input);
end;
function gethash(l,r : longint) : int64;
begin
  gethash := (ha[r]-ha[l-1]*pow[r-l+1] + base*base) mod base;
end;
procedure process;
begin
  assign(output,fo);rewrite(output);
  ha[0] := 0;
  for i:=1 to m do ha[i] := (ha[i-1]*pp + a[i]) mod base;
  pow[0] := 1;
  for i:=1 to m do pow[i] := pow[i-1]*pp mod base;
  hb := 0;
  for i:=1 to n do hb := (hb*pp + b[i]) mod base;
  for i:=1 to m-n+1 do
    if hb = gethash(i,i+n-1) then
      write(i,' ');
  close(output);
end;
begin
  enter;
  process;
end.
    Chủ đề: Hashing, SPOJ Mức độ: