Cod sursa(job #1179916)

Utilizator Mihai_ChihaiMihai Chihai Mihai_Chihai Data 29 aprilie 2014 16:00:40
Problema Potrivirea sirurilor Scor 16
Compilator fpc Status done
Runda Arhiva educationala Marime 0.77 kb
program kmp;
  var t,p,s:ansistring;
      n,m,i,j,sol:longint;

      pr,a:array[1..2500000] of longint;

  begin
    assign(input,'strmatch.in');
    reset(input);
    assign(output,'strmatch.out');
    rewrite(output);
    readln(p);
    readln(t);
    s:=p+'/'+t;
    n:=length(p);
    m:=length(t);

    pr[1]:=0;
    for i:=2 to n+m+1 do
      begin
       j:=pr[i-1];
       while (j>0) and (s[j+1]<>s[i]) do
           j:=pr[j-1];
       if s[j+1]=s[i] then inc(j);
       pr[i]:=j;
      end;

    for i:=1 to m do
      if pr[i+1+n]=n then
        begin
         inc(sol);
         a[sol]:=i-n;
        end;

  writeln(sol);
  for i:=1 to sol do
    begin
      write(a[i],' ');
      if i=1000 then break;
    end;

  close(output);
  end.