Кнут-Моррис-Праттын алгоритм

Кнут-Моррис-Праттын алгоритм (Англи: Knuth–Morris–Pratt algorithm) нь тэмдэгт хайлтын алгоритмын төрөл.

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

n урттай y тэмдэгт мөрөөс m урттай х тэмдэгт мөрийг хайж байна гэж үзье. Тухайн тохиолдолд у тэмдэгт мөрийн j дэх тэмдэгтээс (0≤j<n) эхэлсэн дэд мөртэй х-г харьцуулж байхад х тэмдэгт мөрийн i дэх тэмдэгт нь (0≤i<m) зөрсөн байг. Энэ нь x[0..i-1] = y[j .. j+i-1] = u ба a = x[i] ≠ y[i+j]=b гэсэн үг юм.

Ингэж тэмдэгт зөрсний дараа х тэмдэгт мөрийн эхлэлийг шууд у тэмдэгт мөрийн j+i дугаар байрлалд аваачиж болохгүй. Учир нь х тэмдэгт мөрийг баруун тийш нэг нэг тэмдэгтээр шилжүүлэх үед х тэмдэгт мөрийн эхэнд байрлах ямар нэг v дэд тэмдэгт мөр u тэмдэгтийн төгсгөлийн хэсэгтэй таарч магадгүй. Ийм тохиолдлуудыг орхилгүй шалгахын тулд u тэмдэгт мөрийн хувьд төгсгөл хэсэгтэй нь таарах х тэмдэгт мөрийн эхлэлийн хамгийн урт дэд тэмдэгт мөрийг хил гэж нэрлэе. Мөн програмчлах үед энэ хилийн утгыг олж mpNext[i] элементэд хадгална.

Энэ тохиолдолд a ба b тэмдэгтүүд зөрсний дараа b тэмдэгтийг c=x[mpNext[i]] тэмдэгттэй харьцуулна гэсэн үг. Өөрөөр хэлбэр х тэмдэгт мөрийг strlen(u)-strlen(v) тооны тэмдэгтээр баруун тийш шилжүүлнэ.

Моррис-Праттын алгоритм дахь шилжилт (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];
    }
  }
}