, , : , m ( ) , . , ( Pascal):
Program SimpleSearch;
Var T: array[1..40000] of char; { }
S: array[1..10000] of char; { ; , }
i,j: longint;
m,n: longint;
Begin
{ }
for i:=1 to n-m+1 do
begin
j:=0;
while (j<m) and (S[j+1]=T[i+j]) do { i-}
j:=j+1;
if j=m then { }
writeln(' ',i,'- '); { }
end;
End.
, . , , . . ( ), n, m . , O((n-m+1)m). , - 100 , , , . , , .
, , , , . , aabc ( aab), , , . , , , .
-
, , , , , . , , . , , , ( Dm, D - ), . , , , , 8 .
Program RabinKarpSearch;
Var T: array[1..40000] of 0..9;
S: array[1..8] of 0..9;
i,j: longint;
n,m: longint;
v,w: longint; {v - , , w m }
k: longint;
const D: longint = 10; { (10 )}
Begin
{ }
|
|
|
v:=0;
w:=0;
for i:=1 to m do
begin
v:=v*D+S[i]; { v, }
w:=w*D+T[i]; { w}
end;
k:=1;
for i:=1 to m-1 do {k w Dm-1}
k:=k*D;
for i:=m+1 to n+1 do
begin
if w=v then { , , , }
writeln(' ',i-m,'- ');
if i<=n then
w:=d*(w-k*T[i-m])+T[i]; { w}
end;
End.
(m ) (n ), , O(n+m). , . ? , . , , . , - ( ). , , , . , , (, ), .
Var T: array[1..40000] of char;
S: array[1..10000] of char;
i,j: longint;
n,m: longint;
v,w: longint;
k: longint;
const P: longint = 7919; {1000- }
D: longint = 256; { ( char)}
Begin
{ }
v:=0;
w:=0;
for i:=1 to m do { v w}
begin
v:=(v*D+ord(S[i])) mod P; {ord }
w:=(w*D+ord(T[i])) mod P;
end;
k:=1;
for i:=1 to m-1 do
k:=k*D mod P; {k Dm-1 mod P}
for i:=m+1 to n+1 do
begin
if w=v then { , , }
begin
j:=0;
while (j<m) and (S[j+1]=T[i-m+j]) do
j:=j+1;
if j=m then { }
writeln(' ',i-m,'- ');
end;
if i<=n then
w:=(d*(w+P-(ord(T[i-m])*k mod P))+ord(T[i])) mod P;
end;
End.
, - , ( 1/P ), . , O(m+n+mn/P), mn/P , . , , , . .
, , - --, , .
--
, : -. S[1..i] S S[1..j] (j<i), , ( ). , abcHelloabc abc ( , ). - , , .. abcHelloabc ( ), ( ). 1 m:
|
|
|
var S: array[1..10000] of char;
P: array[1..10000] of word; {, -}
i,k: longint;
m: longint;
Procedure Prefix; {, -}
Begin
P[1]:=0; { }
k:=0;
for i:=2 to m do { 2 m }
begin
while (k>0) and (S[k+1]<>S[i]) do
k:=P[k]; { }
if S[k+1]=S[i] then
k:=k+1;
P[i]:=k; { -}
end;
End;
, - . : ( ) i , i-1. , , , , .. , . , : , ? , -, - m , k. while (P[k]<k), 0, , . k 1 m . , k 2m . , O(m). , .
Program KnutMorrisPrattSearch;
{ Prefix }
var n: longint;
T: array[1..40000] of char;
Begin
{ }
Prefix; { -}
k:=0; { , }
for i:=1 to n do
begin
while (k>0) and (S[k+1]<>T[i]) do
k:=P[k];
if S[k+1]=T[i] then
k:=k+1;
if k=m then { }
begin
writeln(' ',i-m+1,'- ');
k:=P[k];
end;
end;
End.
, , Prefix. , O(n+m), . . .
, -- , . : -- , , . .
P.S. , .
:
, 1
, 2
: - mycm.cm.u
