Mai intai trebuie sa te autentifici.
Cod sursa(job #2609949)
Utilizator | Data | 3 mai 2020 20:50:01 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 40 |
Compilator | fpc | Status | done |
Runda | Arhiva educationala | Marime | 1.03 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]+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.