Cod sursa(job #144225)

Utilizator ProtomanAndrei Purice Protoman Data 27 februarie 2008 13:01:58
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.54 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(s1);
        p:=0;
        h:=0;
        for i:=1 to m 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=n then
                begin
                        inc(h);
                        p:=pi[p];
                        if h<=1000 then
                                v[h]:=i-n;
                end;
        end;
end;

procedure prefix(s:ansistring);
var i,n,p:longint;
begin
        n:=length(s);
        pi[1]:=0;
        p:=0;
        for i:=2 to n 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,s1);
        readln(f1,s2);
        kmp(s1,s2);
        writeln(f2,h);
        if h>1000 then
                h:=1000;
        for i:=1 to h-1 do
                write(f2,v[i],' ');
        if h>0 then
                writeln(f2,v[h]);
        close(f1);
        close(f2);
end.