Cod sursa(job #2609973)

Utilizator Arteni_CristiArteni Cristi Arteni_Cristi Data 3 mai 2020 21:52:53
Problema Potrivirea sirurilor Scor 60
Compilator fpc Status done
Runda Arhiva educationala Marime 1.04 kb
var lps:array[0..2000005] of longint;
    t:array[1..100005] 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
   begin
    if i=1 then
     begin
      lps[j]:=0;
      inc(j)
     end else
    i:=lps[i-1]+1
   end
 end;
i:=1; j:=1;

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

while i<=length(txt) do
 begin
  if txt[i]=pat[j] then
   begin
    inc(i); inc(j)
   end;
  if j=length(pat)+1 then
   begin
    inc(n);
    t[n]:=i-length(pat);
    j:=lps[j-1]+1
   end
  else
   if (i<=length(txt)) and (txt[i]<>pat[j]) then
    if 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

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