Cod sursa(job #186106)

Utilizator dobreDobre Catalin Andrei dobre Data 26 aprilie 2008 18:37:46
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.1 kb
program strmatch;
const fi='strmatch.in';fo='strmatch.out';
var a,b:array[1..2000000]of char;
    pi:array[1..2000000]of longint;
    s:array[0..2000000]of longint;
    n,m:longint;
    i:longint;
    f,g:text;
procedure creare_prefix;
var q,k:longint;
begin
k:=0;
pi[1]:=0;
for q:=2 to m do begin
     while(k>0)and(a[k+1]<>a[q])do k:=pi[k];
     if a[k+1]=a[q] then inc(k);
     pi[q]:=k;
    end;
end;

procedure KMP;
var q,i:longint;
begin
fillchar(pi,sizeof(pi),0);
fillchar(s,sizeof(s),0);
q:=0;
creare_prefix;
for i:=1 to n do begin
     while(q>0)and(a[q+1]<>b[i]) do q:=pi[q];
     if(a[q+1]=b[i])then q:=q+1;
     if q=m then begin
         inc(s[0]);
         s[s[0]]:=i-m;
         q:=pi[q];
        end;
    end;
end;

begin
assign(f,fi);reset(f);
assign(g,fo);rewrite(g);
i:=0;
while not seekeoln(f) do begin
       inc(i);
       read(f,a[i]);
      end;
m:=i;
readln(f);
i:=0;
while not seekeoln(f) do begin
       inc(i);
       read(f,b[i]);
      end;
n:=i;
KMP;
writeln(g,s[0]);
for i:=1 to s[0] do write(g,s[i],' ');
close(f);
close(g);
end.