Cod sursa(job #2609948)

Utilizator Arteni_CristiArteni Cristi Arteni_Cristi Data 3 mai 2020 20:44:29
Problema Potrivirea sirurilor Scor 18
Compilator fpc Status done
Runda Arhiva educationala Marime 1.02 kb
var lps:array[0..2000005] of longint;
    t:array[1..1005] of longint;
    n,i,j:longint;
    txt,pat:ansistring;
begin
assign(input,'strmatch.in'); reset(input);
assign(output,'strmatch.out'); rewrite(output);
readln(pat); readln(txt);
i:=1; j:=2;
while j<=length(pat) do
 begin
  if pat[i]=pat[j] then
   begin
    lps[j]:=i;
    inc(i); inc(j)
   end else
  if (pat[i]<>pat[j]) and (i=1) then
   begin
    lps[j]:=0;
    inc(j)
   end else
  i:=lps[i-1]+1
 end;
i:=1; j:=1;

// n < 1000 conditia problemei (sa nu fi prea mare output ul)

while (i<=length(txt)) and (n<1000) do
 begin
  if txt[i]=pat[j] then
   begin
    inc(i); inc(j);
    if j=length(pat)+1 then
     begin
      inc(n);
      t[n]:=i-length(pat);
      dec(i);
      dec(j);
      j:=lps[j-1]
     end
   end else
  if (txt[i]<>pat[j]) and (j=1) then inc(i) else j:=lps[j-1]+1
 end;
writeln(n);

// write(t[i]-1,' '); in problema indexarea se face de la 0

for i:=1 to n do write(t[i]-1,' ');
close(input);
close(output)
end.