Cod sursa(job #144221)

Utilizator ProtomanAndrei Purice Protoman Data 27 februarie 2008 12:57:29
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.55 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 then
                begin
                        if h<1000 then
                        begin
                                inc(h);
                                v[h]:=i-m;
                        end;
                        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-1 do
                write(f2,v[i],' ');
        if h>0 then
                writeln(f2,v[h]);
        close(f1);
        close(f2);
end.