Pagini recente » Cod sursa (job #1813762) | Cod sursa (job #2702096) | Cod sursa (job #373641) | Cod sursa (job #2909402) | Cod sursa (job #599415)
Cod sursa(job #599415)
const fin = 'strmatch.in'; fout = 'strmatch.out';
type
sir = array[1..2000 * 1000] of char;
urmator = array[1..2000 * 1000] of longword;
pozitii = array[1..1000] of longword;
buffer = array[1..1 shl 20] of char;
var
a, b : sir;
urm : urmator;
pos : pozitii;
buf : buffer;
n ,m ,r : longword;
procedure scanf(var s : sir; var n : longword);
var
c : char;
begin
n := 0;
c := #0;
while not (c in [#10,#26]) do
begin
read( c );
if not (c in [#10,#13,#26]) then
begin
n := n + 1;
s[n] := c;
end;
end;
end;
procedure prefix();
var
i, k : longword;
begin
urm[1] := 0;
k := 0;
for i := 2 to n do
begin
while (k > 0) and (a[i] <> a[k + 1]) do k := urm[k];
if (a[i] = a[k + 1]) then k := k + 1;
urm[i] := k;
end;
end;
procedure kmp();
var
i , k : longword;
begin
k := 0;
for i := 1 to m do
begin
while (k > 0) and (b[i] <> a[k + 1]) do k := urm[k];
if (b[i] = a[k + 1]) then k := k + 1;
if (k = n) then
begin
r := r + 1;
pos[r] := i - n;
k := urm[k];
end;
if (r = 1000) then exit();
end;
end;
procedure main();
var
i : longword;
begin
assign( input, fin ); reset( input );
assign( output, fout ); rewrite( output );
settextbuf( input, buf );
scanf( a, n );
scanf( b, m );
prefix();
kmp();
write( r, #10 );
for i := 1 to r do write( pos[i], #32 );
end;
begin
main();
end.