
Untitled
By: a guest on
Apr 22nd, 2012 | syntax:
Pascal | size: 1.73 KB | hits: 19 | expires: Never
program Project2;
{$APPTYPE CONSOLE}
{$O-}
uses
SysUtils;
const
magic = 99990001;
var
hash1, hash2, ps: array[0..1000100] of longword;
outm: array[1..1000100] of longint;
p, t: string;
i, pos, c: longint;
procedure countp;
var
i: longint;
begin
ps[0]:= 1;
for i:= 1 to length(t) do begin
ps[i]:=ps[i-1]*magic;
end;
end;
procedure makehash1;
var
i: longint;
begin
for i:= 1 to length(t) do begin
hash1[i]:= ord(t[i]) + hash1[i-1]*magic;
end;
end;
procedure makehash2;
var
i: longint;
begin
for i:= 1 to length(p) do begin
hash2[i]:= ord(p[i]) + hash2[i-1]*magic;
end;
end;
function interval1(l, r: longint): longword;
begin
if l > r then begin
result:= 0;
end else begin
result:= hash1[r] - hash1[l-1]*ps[r-l+1];
end;
end;
function interval2(l, r: longint): longword;
begin
if l > r then begin
result:= 0;
end else begin
result:= hash2[r] - hash2[l-1]*ps[r-l+1];
end;
end;
function bsearch(pos: longint): longint;
var
l, r, m: longint;
begin
l:= 0;
r:= length(p) + 1;
while l < r-1 do begin
m:= (l+r)div 2;
if interval1(pos, pos+m-1)=interval2(1, m) then begin
l:= m;
end else begin
r:= m;
end;
end;
result:= l+1;
end;
begin {
reset(input,'input.txt');
rewrite(output,'output.txt'); }
readln(p);
readln(t);
//hash1 - t, hash2 - p
countp;
makehash1;
makehash2;
for i:= 1 to length(t) - length(p)+1 do begin
pos:= bsearch(i);
if interval1(i+pos, i+length(p)-1) = interval2(pos+1, length(p)) then begin
inc(c);
outm[c]:= i;
end;
end;
writeln(c);
for i:= 1 to c do begin
write(outm[i],' ');
end;
end.