Cod sursa(job #1365789)

Utilizator mariusadamMarius Adam mariusadam Data 28 februarie 2015 15:38:03
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.29 kb
program KMP;
var     x1,y1,z:ansistring;
        pi,d:array[0..2000000] of longint;
        x,y:array[1..2000000] of char;
        bufin,bufout:array[1..400000] of char;
        n,m,i,k,nr:longint;
        f,g:text;

procedure construct_pi;
var k,i:longint;
begin
 pi[1]:=0;
 k:=0;
 for i:=2 to n do
 begin
        while(k>0)and(x[i]<>x[k+1]) do
                k:=pi[k];
        if x[i]=x[k+1] then
                k:=k+1;
        pi[i]:=k;
 end;
end;

begin
 assign(f,'strmatch.in'); reset(f);
 assign(g,'strmatch.out'); rewrite(g);
 settextbuf(f,bufin);
 settextbuf(f,bufout);
 readln(f,x1);
 readln(f,y1);
 n:=length(x1);
 m:=length(y1);
 if n>m then
 begin
        z:=x1;
        x1:=y1;
        y1:=z;
 end;
 for i:=1 to n do
  x[i]:=x1[i];
 for i:=1 to m do
  y[i]:=y1[i];
 construct_pi;
 k:=0;
 for i:=1 to m do
 begin
        while (k>0)and(y[i]<>x[k+1]) do
                k:=pi[k];
        if y[i]=x[k+1] then
                k:=k+1;
        d[i]:=k;
        if k=n then
                nr:=nr+1;
 end;
 writeln(g,nr);
 k:=0;
 for i:=1 to m do
        if d[i]=n then
        begin
                write(g,i-n,' ');
                k:=k+1;
                if k=1000 then
                        break;
        end;
 close(f);
 close(g);
end.