Cod sursa(job #872170)

Utilizator Buzu_Tudor_RoCont vechi Buzu_Tudor_Ro Data 5 februarie 2013 20:55:49
Problema Potrivirea sirurilor Scor 36
Compilator fpc Status done
Runda Arhiva educationala Marime 1.28 kb
Program p1;
var fi,fo:text; i,k,n,m,nrsol:longint;
    a,b:array[0..2000001] of char; r:set of char;
    p:array[0..2000001] of longint;
    sol:array[0..1009] of longint;
    bufi:array[0..1 shl 20] of char;
begin
    assign(fi,'strmatch.in'); reset(fi);
    settextbuf(fi,bufi);
    assign(fo,'strmatch.out'); rewrite(fo);
    read(fi,a); readln(fi); read(fi,b); nrsol:=0;
    p[1]:=0; k:=0; m:=1; n:=1; r:=['A'..'Z']+['a'..'z']+['0'..'9'];
    while a[m] in r do m:=m+1;
    while b[n] in r do n:=n+1;
    m:=m-1; n:=n-1;

    for i:=2 to m do begin
                     while (k>0) and (a[k+1]<>a[i]) do k:=p[k];
                     if a[k+1]=a[i] then k:=k+1;
                     p[i]:=k;
                     end;

    k:=0;
    for i:=1 to n do begin
                     while (k>0) and (a[k+1]<>b[i]) do k:=p[k];
                     if a[k+1]=b[i] then k:=k+1;
                     if k=m then begin
                                 k:=p[m];
                                 nrsol:=nrsol+1;
                                 if nrsol<=1000 then sol[nrsol]:=i-m;
                                 end;
                     end;

    writeln(fo,nrsol);
    if nrsol>1000 then nrsol:=1000;
    for i:=1 to nrsol do write(fo,sol[i],' ');
    close(fi); close(fo);
end.