Cod sursa(job #144213)

Utilizator ProtomanAndrei Purice Protoman Data 27 februarie 2008 12:46:24
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.6 kb
var f1,f2:text;
    s1,s2:array[0..2000010] of char;
    i,h,m,n:longint;
    c:char;
    v:array[0..1024] of longint;
    pi:array[0..2000010] of longint;

procedure prefix;forward;

procedure kmp;
var i,p:longint;
begin
        prefix;
        p:=0;
        h:=0;
        for i:=1 to n do
        begin
                while (p>0)and(s1[i]<>s2[p+1]) do
                        p:=pi[p];
                if s1[i]=s2[p+1] then
                        inc(p);
                if (p=m)and(h<=1000) then
                begin
                        inc(h);
                        v[h]:=i-m;
                        p:=pi[p];
                end;
        end;
end;

procedure prefix;
var i,p:longint;
begin
        pi[1]:=0;
        p:=0;
        for i:=2 to m do
        begin
                while (p>0)and(s2[i]<>s2[p+1]) do
                        p:=pi[p];
                if s2[i]=s2[p+1] then
                        inc(p);
                pi[i]:=p;
        end;
end;

begin
        assign(f1,'strmatch.in');
        reset(f1);
        assign(f2,'strmatch.out');
        rewrite(f2);
        while not eoln(f1) do
        begin
                read(f1,c);
                inc(i);
                s2[i]:=c;
        end;
        readln(f1);
        m:=i;
        i:=0;
        while not eoln(f1) do
        begin
                read(f1,c);
                inc(i);
                s1[i]:=c;
        end;
        n:=i;
        kmp;
        writeln(f2,h);
        for i:=1 to h do
                write(f2,v[i],' ');
        close(f1);
        close(f2);
end.