Cod sursa(job #243357)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 12 ianuarie 2009 19:22:54
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.33 kb
var p,t:array[1..2000001] of char;
    n,m,l,q,k:longint;
    v,vv:array[1..2000001] of longint;
    ok:boolean;
procedure prefix;inline;
    begin
      k:=0; v[1]:=0;
      for q:=2 to m do
        begin
          while (k>0)and(p[k+1]<>p[q]) do k:=v[k];
          if p[k+1]=p[q] then inc(k);
          v[q]:=k;
        end;
    end;
procedure kmp;inline;
    begin
      k:=0; l:=0;
for q:=1 to n do
   begin
     while (k>0)and(p[k+1]<>t[q]) do k:=v[k];
     if p[k+1]=t[q] then inc(k);
     if k=m then
        begin
         inc(l);
         if l<=1000 then vv[l]:=q-m;
         k:=v[k];
        end;
   end;
    end;

begin
assign(input,'strmatch.in'); reset(input);
readln(p);
m:=1;
while ord(p[m])<>0 do {not seekeoln do begin} inc(m);{ read(p[m]); end;   }dec(m);
n:=0;
readln(t);
while ord(t[n])<>0 do {not seekeoln do begin }inc(n);{read(t[n]); end;} dec(n);
close(input);
assign(output,'strmatch.out'); rewrite(output);
if m=n then
  begin
    ok:=true;
    k:=1;
    while (k<=n)and(ok) do
      begin
        if p[k]<>t[k] then ok:=false;
        inc(k);
      end;
    if ok then begin writeln('1'); writeln('0');end
          else writeln('0');
  end
       else
  begin
prefix;
kmp;
writeln(l);
if l>1000 then l:=1000;
for k:=1 to l do write(vv[k],' ');
  end;
close(output);
end.