Cod sursa(job #1179446)

Utilizator Mihai_ChihaiMihai Chihai Mihai_Chihai Data 28 aprilie 2014 18:53:53
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.17 kb
  program strmatch;
    var p,t,s:array[0..2000000] of char;
        n,m,i,j,l,r,ans:longint;
        z,sol:array[0..2000000] of longint;
        c:char;
    function min(a,b:longint):longint;
     begin
       if a<b then min:=a else min:=b;
     end;

    begin
    assign(input,'strmatch.in');
    reset(input);
    assign(output,'strmatch.out');
    rewrite(output);
    i:=-1;
    while not eof do begin
       inc(i);
       read(c);
       s[i]:=c;
       if eoln then if n=0 then
                begin
                n:=i+1;
                inc(i);
                s[i]:='^';
                readln;
                end;
       end;

    m:=i+1;

    z[0]:=0;
    for i:=1 to m-1 do
       begin
       if i<=r then z[i]:=min(z[i-l],r-i+1);
       while (i+z[i]<m) and (s[z[i]]=s[i+z[i]]) do inc(z[i]);
       if i+z[i]-1>r then begin
                l:=i;
                r:=i+z[i]-1;
                       end;
       end;

   for i:=0 to m-n-1  do
      if z[i+n+1]=n then
        begin
         inc(ans);
         sol[ans]:=i;
        end;
    writeln(ans);
    for i:=1 to ans do write(sol[i],' ');
    close(output);
    end.