Don't like ads? PRO users don't see any ads ;-)
Guest

Untitled

By: a guest on Apr 22nd, 2012  |  syntax: Pascal  |  size: 1.73 KB  |  hits: 19  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. program Project2;
  2.  
  3. {$APPTYPE CONSOLE}
  4. {$O-}
  5. uses
  6.   SysUtils;
  7.  
  8. const
  9.   magic = 99990001;
  10. var
  11.   hash1, hash2, ps: array[0..1000100] of longword;
  12.   outm: array[1..1000100] of longint;
  13.   p, t: string;
  14.   i, pos, c: longint;
  15. procedure countp;
  16. var
  17.   i: longint;
  18. begin
  19.   ps[0]:= 1;
  20.   for i:= 1 to length(t) do begin
  21.     ps[i]:=ps[i-1]*magic;
  22.   end;
  23. end;
  24.  
  25. procedure makehash1;
  26. var
  27.   i: longint;
  28. begin
  29.   for i:= 1 to length(t) do begin
  30.     hash1[i]:= ord(t[i]) + hash1[i-1]*magic;
  31.   end;
  32. end;
  33.  
  34. procedure makehash2;
  35. var
  36.   i: longint;
  37. begin
  38.   for i:= 1 to length(p) do begin
  39.     hash2[i]:= ord(p[i]) + hash2[i-1]*magic;
  40.   end;
  41. end;
  42.  
  43. function interval1(l, r: longint): longword;
  44. begin
  45.   if l > r then begin
  46.     result:= 0;
  47.   end else begin
  48.     result:= hash1[r] - hash1[l-1]*ps[r-l+1];
  49.   end;
  50. end;
  51.  
  52. function interval2(l, r: longint): longword;
  53. begin
  54.   if l > r then begin
  55.     result:= 0;
  56.   end else begin
  57.     result:= hash2[r] - hash2[l-1]*ps[r-l+1];
  58.   end;
  59. end;
  60.  
  61. function bsearch(pos: longint): longint;
  62. var
  63.   l, r, m: longint;
  64. begin
  65.   l:= 0;
  66.   r:= length(p) + 1;
  67.   while l < r-1 do begin
  68.     m:= (l+r)div 2;
  69.     if interval1(pos, pos+m-1)=interval2(1, m) then begin
  70.       l:= m;
  71.     end else begin
  72.       r:= m;
  73.     end;
  74.   end;
  75.   result:= l+1;
  76. end;
  77.  
  78. begin      {
  79.   reset(input,'input.txt');
  80.   rewrite(output,'output.txt'); }
  81.  
  82.   readln(p);
  83.   readln(t);
  84.   //hash1 - t, hash2 - p
  85.   countp;
  86.   makehash1;
  87.   makehash2;
  88.  
  89.   for i:= 1 to length(t) - length(p)+1 do begin
  90.     pos:= bsearch(i);
  91.     if interval1(i+pos, i+length(p)-1) = interval2(pos+1, length(p)) then begin
  92.       inc(c);
  93.       outm[c]:= i;
  94.     end;
  95.   end;
  96.   writeln(c);
  97.   for i:= 1 to c do begin
  98.     write(outm[i],' ');
  99.   end;
  100. end.