Cod sursa(job #1598204)

Utilizator iondodon1998Dodon Ion iondodon1998 Data 12 februarie 2016 18:05:58
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.36 kb
Program potriviresir;
type    tabelpi=array[0..2000010] of longint;
            solutie=array[1..2000010] of longint;
var a,b:ansistring;
        pi:tabelpi;
        sol:solutie;
        la,lb,i,r:longint;
        f1,f2:text;

Procedure prefix;
    var i,k:longint;
    begin
        k:=0;
        pi[1]:=0;
        for i:=2 to la do
            begin
                while (k>0) and (a[k+1]<>a[i]) do
                    k:=pi[k];
                if a[k+1]=a[i] then
                    k:=k+1;
                pi[i]:=k;
            end;
    end;

Procedure KMP;
    var i,k:longint;
begin
    k:=0;
    for i:=1 to lb do
        begin
            while (k>0) and (b[i]<>a[k+1]) do
                k:=pi[k];
            if a[k+1]=b[i] then
                k:=k+1;
            if k=la then
                begin
                    r:=r+1;
                    sol[r]:=i-la;
                end;
        end;
end;

begin
    assign(f1,'strmatch.in'); reset(f1);
    assign(f2,'strmatch.out'); rewrite(f2);

    readln(f1,a);
    la:=length(a);
    readln(f1,b);
    lb:=length(b);

    r:=0;
    if la<lb then
            begin
                prefix;
                KMP;
            end;

    writeln(f2,r);
    if r>1000 then r:=1000;
    for i:=1 to r do
        write(f2,sol[i],' ');

    close(f1);
    close(f2);
end.