Cod sursa(job #2405505)

Utilizator AlexNeaguAlexandru AlexNeagu Data 14 aprilie 2019 16:21:01
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.95 kb
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 17] 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;
                        if (r < 1001) then pos[r] := i - n;
                        k := urm[k];
                end;
        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 );
        if (r > 1000) then r := 1000;
        for i := 1 to r do write( pos[i], #32 );
end;


begin
        main();
end.