Cod sursa(job #202265)

Utilizator cypherMircea Grecu cypher Data 7 august 2008 08:57:16
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.36 kb
program strmatch;
var a,p:array[1..2000000] of char;
    next:array[1..2000000] of word;
	b:array[1..1000] of longint;
    n,m,k:longint;

    procedure citire;
    var f:text;
        i,j:word;
    begin
		m:=0; n:=0; k:=0;
        assign(f,'strmatch.in');
        reset(f);
        while not eoln(f) do begin
			inc(m);
			read(f,p[m]);
        end;
		readln(f);
        while not eoln(f) do begin
			inc(n);
			read(f,a[n]);
		end;
        close(f);
    end;

    procedure initnext;
    var i,j:longint;
    begin
        i:=1; j:=0; next[1]:=0;
        repeat
          if (j=0) or (p[i]=p[j])
            then begin i:=i+1; j:=j+1; next[i]:=j end
            else begin j:=next[j] end;
        until i>M;
    end;

    procedure count;
    var i,j:longint;
    begin
        i:=1; j:=1; k:=0;
        repeat
			if (j=0) or (a[i]=p[j]) then begin inc(i); inc(j); end
			else j:=next[j];
			if j>M then begin 
				inc(k);
				if k<=1000 then b[k]:=i-m-1;
				j:=next[j]; 
			end;
        until (i>N);
    end;

    procedure scriere;
    var f:text; i:longint;
    begin
		assign(f,'strmatch.out');
		rewrite(f);
		writeln(f,k);
		if k>1000 then k:=1000;
		if k>0 then write(f,b[1]);
		for i:=2 to k do write(f,' ',b[i]);
		writeln(f);
        close(f);
    end;

BEGIN
    citire;
    initnext;
	count;
    scriere;
END.