Cod sursa(job #1402823)

Utilizator Stefan.Andras Stefan Stefan. Data 26 martie 2015 21:12:24
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.78 kb
//KMP ^_^.
program kmp;
const lungmax = 2000001;
      pozitii = 1001;
var f,g:text;
    bufin,bufout:array[1..1 shl 17] of char;
    T, P:ansistring;
    urm:array[1..lungmax] of longint;
    v:array[1..pozitii] of longint;
    n,m,i,q,k:longint;
//----------------------------
procedure urmatorul(p:ansistring);
var k,m,q:longint;
begin
        m := length(p);
        urm[1] := 0;
        k := 0;
        for q := 2 to m do
                begin
                while (k > 0) and (p[k+1] <> p[q]) do k := urm[k];
                if p[k+1] = p[q] then inc(k);
                urm[q] := k;
                end;

end;
//---------------------------
procedure swap(var x,y:ansistring);
var aux:ansistring;
begin
        aux := x; x := y; y := aux;
end;
//---------------------------
procedure adauga(x:longint);
begin
        inc(k); v[k]:=x;
end;
begin
        assign(f,'strmatch.in'); reset(f);
        assign(g,'strmatch.out'); rewrite(g);
        settextbuf(f,bufin); settextbuf(f,bufout);
        readln(f,T); readln(f,P); swap(T, P);
        n := length(t);
        m := length(p);
        urmatorul(P);
        q := 0;   k :=0;
        for i := 1 to n do
                begin
                while (q > 0) and (p[q+1] <> t[i]) do q := urm[q];
                if p[q+1] = t[i] then inc(q);
                if q = m then
                        begin
                        //  writeln(g,i-m);
                          if k < 1000 then adauga(i-m)
                                 else inc(k);
                          q := urm[q];
                        end;
                end;
        writeln(g,k);
        if k > 1000 then
                k:=1000;
        for i := 1 to k do
                write(g,v[i],' ');
        close(f); close(g);
end.