Cod sursa(job #416671)

Utilizator lianaliana tucar liana Data 13 martie 2010 10:57:01
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.36 kb
program kmp;
var f, g:text;
    p,t:array[1..2000000] of char;
    l, poz:array[1..1000] of longint;
    m, n, nr:longint;

procedure citire;
  begin
    while not seekeoln(f) do
      begin
        m:=m+1;
        read(f,p[m]);
      end;
    readln(f);
    while not seekeoln(f) do
      begin
        n:=n+1;
        read(f,t[n]);
      end;
  end;

procedure prefix;
var k, i:longint;
  begin
    k:=0;
    l[1]:=0;
    for i:=2 to m do
      begin
        k:=l[i-1];
        while (k>0) and (p[k+1]<>p[i]) do
          k:=l[k];
        if p[k+1]=p[i] then
          k:=k+1;
        l[i]:=k;
      end;
  end;

procedure rezolvare;
var k, i:longint;
  begin
    k:=0;
    for i:=1 to n do
      begin
        while (k>0) and (t[i]<>p[k+1]) do
          k:=l[k];
        if t[i]=p[k+1] then
          k:=k+1;
        if k=m then
          begin
            nr:=nr+1;
            if nr<=1000 then
              poz[nr]:=i-m;
            k:=l[k];
          end;
      end;
  end;

procedure afisare;
var i:longint;
  begin
    writeln(g,nr);
    if nr>1000 then
      nr:=1000;
    for i:=1 to nr do
      write(g,poz[i],' ');
  end;

  begin
    assign(f,'strmatch.in'); reset(f);
    assign(g,'strmatch.out'); rewrite(g);
    citire;
    prefix;
    rezolvare;
    afisare;
    close(f);
    close(g);
  end.