Cod sursa(job #202268)

Utilizator cypherMircea Grecu cypher Data 7 august 2008 09:17:44
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.3 kb
program strmatch;
var a,p:array[0..2000010] of char;
    next:array[0..2000010] 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;
        for i:=1 to m do begin
			while (j>0) and (p[i]<>p[j]) do j:=next[j];
            inc(j);
			next[i+1]:=j;
        end;
    end;

    procedure count;
    var i,j:longint;
    begin
        j:=1;
        for i:=1 to n do begin
			while (j>0) and (a[i]<>p[j]) do j:=next[j];
			inc(j);
			if j>m then begin
				inc(k);
				if k<=1000 then b[k]:=i-m;
				j:=next[j];
			end;
        end;
    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.