Pagini recente » Cod sursa (job #3220179) | Cod sursa (job #956722) | Cod sursa (job #282170) | Cod sursa (job #1290934) | Cod sursa (job #566675)
Cod sursa(job #566675)
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.