Дэд тэмдэгт мөр хайх Морисс-Праттын алгоритм

Энэ алгоритм нь бүх боломжийг шалгах алгоритмын үед хийгдэж байсан х тэмдэгт мөрийн зүүнээс баруун тийш чиглэлтэй, нэг тэмдэгтийн алхамтай шилжилтүүдийн алхмыг уртасган, тоог багасгадаг.


n урттай y тэмдэгт мөрөөс m урттай х тэмдэгт мөрийг хайж байна гэж үзье. Тухайн тохиолдолд у тэмдэгт мөрийн j дэх тэмдэгтээс (0≤j
Моррис-Праттын алгоритм дахь шилжилт (v нь u-гийн хил болно)

Алгоритмын бэлтгэл ажиллагаа болох mpNext хүснэгтийг байгуулах хугацаа O(m) ба ажиллах нийт хугацааг O(n+m) гэж үнэлж болно.

Жишээ:
void preMp(char *x, int m, int mpNext[]) {
int i, j;

i = 0;
j = mpNext[0] = -1;
while (i < m) { while (j > -1 && x[i] != x[j])
j = mpNext[j];
mpNext[++i] = ++j;
}
}


void MP(char *x, int m, char *y, int n) {
int i, j, mpNext[XSIZE];

/* Preprocessing */
preMp(x, m, mpNext);

/* Searching */
i = j = 0;
while (j < n) { while (i > -1 && x[i] != y[j])
i = mpNext[i];
i++;
j++;
if (i >= m) {
OUTPUT(j - i);
i = mpNext[i];
}
}
}