Cod sursa(job #302554)

Utilizator SprzlAbcdefg Sprzl Data 8 aprilie 2009 23:44:16
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.96 kb
program kmp;
var a,b:array [1..2000002] of char;
    nrsol,i,k,m,n:longint;
    pi:array [1..2000002] of word;
    sol:array [1..1000] of longint;
begin
  assign(input,'strmatch.in');
  assign(output,'strmatch.out');
  reset(input);
  rewrite(output);
  readln(a);
  readln(b);
  i:=1;
  while a[i]<>#0 do
    inc(i);
  m:=i-1;

  i:=1;
  while b[i]<>#0 do
    inc(i);
  n:=i-1;
  k:=0;
  pi[1]:=0;
  for i:=2 to m do
  begin
    while (k>0) and (a[k+1]<>a[i]) do
      k:=pi[k];
    if a[k+1] = a[i] then
      inc(k);
    pi[i]:=k;
  end;

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

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