note: This article comes from the Internet. Please contact me via lethic@163.com if there is any infringement.
lethic@163.com.

MM

KMPKMPBAABA=”I’m matrix67″B=”matrix”BAMM
ABAnBmO (mn)mnA= “aaaaaaaaaaaaaaaaaaaaaaaaaab”B=”aaaaaaaab”O(n) m<=nKMP KMPKnuthMorrisPrattAVL AVLBellman-Ford3x+1 KMP(shift)NextKMPKMP A="abababaababacb"B="ababacb"KMPijA[i-j+ 1..i]B[1..j]iijjA[i]jB jjA[i+1]B[j+1]A[i+1]=B[j+1]ijj=mBABiA[i+1]<>B[j+1]KMPjjA[i-j+1..i]B[1..j]B[j+1]A[i+1]ij i=j=5

i = 1 2 3 4 5 6 7 8 9
A = a b a b a b a a b a b
B = a b a b a c b
j = 1 2 3 4 5 6 7

A[6]<>B[6]j5jj’j’j’B[1..j]j’j’jj’ijj’B [1..5]=”ababa”33″aba”j3A[6]B[4]i6j 4

i = 1 2 3 4 5 6 7 8 9
A = a b a b a b a a b a b
B = a b a b a c b
j = 1 2 3 4 5 6 7

jiBP[j]Bjj+1jP[j]B[1..P[j]]=B[j-P[j]+1..j]
A[7]=B[5]ij1A[i+1]<>B[j+1]

i = 1 2 3 4 5 6 7 8 9
A = a b a b a b a a b a b
B = a b a b a c b
j = 1 2 3 4 5 6 7

P[5]=3j=3

i = 1 2 3 4 5 6 7 8 9
A = a b a b a b a a b a b
B = a b a b a c b
j = 1 2 3 4 5 6 7

j=3A[i+1]=B[j+1]jjP[3]

i = 1 2 3 4 5 6 7 8 9
A = a b a b a b a a b a b
B = a b a b a c b
j = 1 2 3 4 5 6 7

i7j1A[8]B[j+1]jP[1]0

i = 1 2 3 4 5 6 7 8 9
A = a b a b a b a a b a b
B = a b a b a c b
j = 0 1 2 3 4 5 6 7

A[8]=B[1]i8j1j0A[i+1]=B[j+1]A[8]=”d”j=0ijA[i]=B[1]

j:=0;
for i:=1 to n do
begin
while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
if B[j+1]=A[i] then j:=j+1;
if j=m then
begin
writeln(‘Pattern occurs with shift ‘,i-m);
j:=P[j];
end;
end;

j:=P[j]
iforAB

P
O(n)whileKMPj whilejjj1jn1jnjnjwhilenforforO(1)O(n)PO(m)
PO(m^2)O(m^3)P[1],P[2],…,P[j-1]P[j]B=”ababacb”P[1],P[2],P[3]P[4]P[5]P[6]P[4]=2P [5]P[4]+1P[4]B[1,2]B[3,4]B[3]=B[5]P[5]P[4] P[6]P[5]+1B[ P[5]+1 ]<>B[6]P[6]P[5]P[6]=P[ P[5] ]+1

1 2 3 4 5 6 7
B = a b a b a c b
P = 0 0 1 2 3 ?

P[5]=3B[1..3]B[3..5]”aba”P[3]=1B[1]B[3]B[5]”a”P[6]P[5]P[3]B[2]B[6]P[6]P[3]+1P[6]P[3]B[2]<>B[6]P[1]P[6]=0
KMPKMPB

P[1]:=0;
j:=0;
for i:=2 to m do
begin
while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
if B[j+1]=B[i] then j:=j+1;
P[i]:=j;
end;

KMPBBABA

BitComet
Dr.eyeBabylon