fork download
  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
stdin
Standard input is empty
stdout
0