Cod sursa(job #144203)

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

procedure prefix(s:ansistring);forward;

procedure kmp(s1,s2:ansistring);
var i,n,m,p:longint;
begin
        n:=length(s1);
        m:=length(s2);
        prefix(s2);
        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(s:ansistring);
var i,m,p:longint;
begin
        m:=length(s);
        pi[1]:=0;
        p:=0;
        for i:=2 to m do
        begin
                while (p>0)and(s[i]<>s[p+1]) do
                        p:=pi[p];
                if s[i]=s[p+1] then
                        inc(p);
                pi[i]:=p;
        end;
end;

begin
        assign(f1,'strmatch.in');
        reset(f1);
        assign(f2,'strmatch.out');
        rewrite(f2);
        readln(f1,s2);
        readln(f1,s1);
        kmp(s1,s2);
        writeln(f2,h);
        for i:=1 to h do
                write(f2,v[i],' ');
        close(f1);
        close(f2);
end.