Cod sursa(job #298554)

Utilizator SprzlAbcdefg Sprzl Data 6 aprilie 2009 10:59:45
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.09 kb
program kmp;
var a,b:array [1..2000000] of char;
    f:array [1..2000000] of longint;
    sol:array [1..1000] of longint
    nrsol,i,k,m,n,q:longint;
function min(a,b:longint):longint;
begin
  min:=a;
  if b<a then
    min:=b;
end;

begin
  assign(input,'strmatch.in');
  assign(output,'strmatch.out');
  reset(input);
  rewrite(output);


  m:=0;
  n:=0;

  while not(eoln) do
  begin
    inc(m);
    read(a[m]);
  end;
  readln;
  while not(eoln) do
  begin
    inc(n);
    read(b[n]);
  end;

  k:=0;
  f[1]:=0;

  nrsol:=0;

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

  q:=0;

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


  writeln(nrsol);
  for i:=1 to min(nrsol,1000) do
    write(sol[i],' ');

  close(input);
  close(output);
end.