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

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


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];
}
}
}

74. Ганнибал (Hannibal Barca)

"Тайван байдалдаа орсон улсыг зөвхөн зэр зэвсгийн дуу л сэрээж чадна"

(МЭӨ 247-183)



МЭӨ III зууны үед Газрын дундад тэнгисийн баруун хэсэгт Ромоос гадна Карфаген гэсэн хүчирхэг улс байжээ. Эдгээр улсууд ноёрхох байр суурийн төлөө урт удаан хугацааны, хатуу ширүүн дайныг эхлүүлсэн байна. Пунийн гэж нэрлэгдэх гурван дайн болж өнгөрчээ. Эцсийн эцэст Ромчууд тэмцэлд ялсан байна. Гэвч тэдний хойч үеийнхэн олон зууны дараа ч гэсэн Пунийн II дайны үед Ромын оршин суугчдад аймшиг төрүүлж байсан карфагены жанжин Ганнибалын тухай дурссаар байлаа. Ромынхны хувьд "Ганнибал гадаа ирлээ!" гэсэн үг нь хүмүүсийг асар их аюулаас сэрэмжлүүлэн, болгоомжтой байхыг анхааруулсан үг болон хувирсан байна.
Өөр нэг зүйл нь карфагены жанжны тухай зөвхөн ромын түүхчдийн бүтээлээс л олж уншиж болдог явдал билээ. Гайхалтай нь тэд өөрийн заналт дайсны тухай их л биширсэн, хүндэтгэсэн байдалтайгаар бичсэн байдаг юм.