fork(2) download
copy 
  1. {$H+}
  2. uses math;
  3. const
  4.   fi='';//paliny.inp';
  5.   fo='';//paliny.out';
  6.   maxn=50003;
  7.   pp=307;
  8.   base=trunc(1e9)+7;
  9. var
  10.   i,j,n,d,c,g,top,ans : longint;
  11.   ha,hb,pow : array[0..maxn] of int64;
  12.   a : array[1..maxn] of longint;
  13.   s : string;
  14. function gethash1(l,r : longint) : int64;
  15.   begin
  16.     gethash1 := (ha[r] - ha[l-1] * pow[r-l+1] + base * base) mod base;
  17.   end;
  18. function gethash2(l,r : longint) : int64;
  19.   begin
  20.     gethash2 := (hb[r] - hb[l+1] * pow[l-r+1] + base * base) mod base;
  21.   end;
  22. function ok ( le : longint) : boolean;
  23.   var i,j : longint;
  24.   begin
  25.     for i := 1 to n - le + 1 do
  26.       if gethash1(i,i+le-1) = gethash2(i+le-1,i) then exit(true);
  27.     exit(false);
  28.   end;
  29. procedure process;
  30.   begin
  31.   d := 1 ;
  32.   c := top ;
  33.   g := (d+c) div 2;
  34.   while (G<>d) and (g<>C) do
  35.     begin
  36.       if ok (a[g]) then d := g else c := g;
  37.       g := (d+c) div 2;
  38.     end;
  39.   for g := c downto d do
  40.     if ok (a[g]) then
  41.       begin
  42.         ans := max(ans,a[g]);
  43.         exit;
  44.       end;
  45.   end;
  46. procedure push(x : longint);
  47.   begin
  48.     inc(top);
  49.     a[top] := x;
  50.   end;
  51. begin
  52.   assign(input,fi);reset(input);
  53.   assign(output,fo);rewrite(output);
  54.   readln(n);
  55.   readln(s);
  56.   pow[0] := 1;
  57.   for i := 1 to n do pow[i] := pow[i-1] * pp mod base;
  58.   for i := 1 to n do ha[i] := ( ha[i-1] * pp + ord(s[i]) ) mod base;
  59.   for i := n downto 1 do hb[i] := ( hb[i+1] * pp + ord(s[i]) ) mod base;
  60.   top := 0;
  61.   for i := 1 to n do
  62.     if i mod 2 = 0 then push(i);
  63.   process;
  64.   top := 0;
  65.   for i := 1 to n do
  66.     if i mod 2 = 1 then push(i);
  67.   process;
  68.   writeln(ans);
  69.   close(input);close(output);
  70. end.
  71.  
  72.  
Success #stdin #stdout 0s 1964KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/cMK4Bp
problem PALINY, based on SPOJ submission 15973843 (PAS-FPC), 2015-12-30 14:36:24
language:
Pascal (fpc 3.0.4)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!