Cod sursa(job #566675)

Utilizator promix2012petruta andrei promix2012 Data 29 martie 2011 10:45:24
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 0.94 kb
Program KMP;
Const nMax = 10000;
mMax = 10000;
Var Urm: Array[1..mMax] Of Byte;
T, P: ansiString;
n, m, q, i,nr: longint;
f, g: Text;
v:array[1..10000] of longint;
Procedure Urmatorul(P: ansiString);
Var k, m, q: Byte;
Begin
m := Length(P);
Urm[1] := 0;
k := 0;
For q := 2 To m Do
{determina lungimea celui mai lung prefix al lui P
care este si sufix al subsirului P[1..q] }
Begin
While (k>0) And (P[k+1]<>P[q]) Do k := Urm[k];
If P[k+1]=P[q] Then Inc(k);
Urm[q] := k
End
End;
Begin
Assign(f, 'strmatch.IN'); Reset(f);
Assign(g, 'strmatch.OUT'); ReWrite(g);

ReadLn(f, p);
ReadLn(f, t);
n := Length(t);
m := Length(p);
Urmatorul(P);
q := 0;
nr:=0;
For i := 1 To n Do
Begin
While (q>0) And (P[q+1]<>T[i]) Do q := Urm[q];
If P[q+1]=T[i] Then Inc(q); {s-a mai gasit un caracter corect}
If q=m Then
Begin
inc(nr);
v[nr]:=i-m;
q := Urm[q]
End
End;
writeln(g,nr);
for i:=1 to nr do
write(g,v[i],' ');
Close(g)
End.