Cod sursa(job #1072857)

Utilizator Mihai_ChihaiMihai Chihai Mihai_Chihai Data 5 ianuarie 2014 00:26:44
Problema Potrivirea sirurilor Scor 24
Compilator fpc Status done
Runda Arhiva educationala Marime 0.79 kb
program kmp;
var t,p:ansistring;
     urm,a:array[1..2000000] of longint;
     n,m,i,q,j:longint;

procedure urmatorul(p:string);
var k:longint;
begin
  m:=length(p);
  k:=0;
  urm[1]:=0;
  for q:=2 to n 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;

begin
assign(input,'strmatch.in');  reset(input);
assign(output,'strmatch.out'); rewrite(output);
readln(p);
readln(t);
n:=length(t);
urmatorul(p);
q:=0;
j:=0;
for i:=1 to n do
  begin
    while (p[q+1]<>t[i])  and (q>0) do q:=urm[q];
    if p[q+1]=t[i] then inc(q);
    if q=m then
      begin
        inc(j);
        a[j]:=i-m;
        q:=urm[q];
      end;
  end;
writeln(j);
for i:=1 to j do write(a[i],' ');
close(output);
end.