C11STR2 – spoj

July 25, 2017 by Leave a Comment

Đề bài:

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:

{$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
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 độ: