Если мы смотрим только на то, что случается с j в течение алгоритма выше, это - сорт подобных конечный автомат. При каждом шаге j установлен любой в j+1 (во внутреннем цикле, после соответствия) или к перекрытию o (после того, как несоответствие). При каждом шаге значение o - только функция j и не зависит от другой информации подобно символам в T []. Так что мы можем нарисовать кое-что подобно автомату, со стрелками, подключающими значения j и помеченный парами и несоответствиями.

Различие между этим и автоматами, к которым мы используемся - то, что это имеет только две стрелки из каждого круга, вместо один в символ. Но мы можем все еще моделировать это точно так же как любой другой автомат, помещая маркер на состоянии начала (j=0) и перемещая это вокруг стрелок. Всякий раз, когда мы получаем символ соответствия в T [], мы переходим к следующему символу текста. Но всякий раз, когда мы получаем несоответствие, мы смотрим на тот же самый символ в следующем шаге, если бы не случай несоответствия в состоянии j=0.

Так в этом примере (то же самое как тот выше) автомат проходит последовательность состояний:

    j=0
            mismatch T[0] != "n"
    j=0
            mismatch T[1] != "n"
    j=0
            match T[2] == "n"
    j=1
            match T[3] == "a"
    j=2
            match T[4] == "n"
    j=3
            mismatch T[5] != "o"
    j=1
            match T[5] == "a"
    j=2
            match T[6] == "n"
    j=3
            match T[7] == "o"
    j=4
            found match
    j=0
            mismatch T[8] != "n"
    j=0
            mismatch T[9] != "n"
    j=0
            match T[10] == "n"
    j=1
            mismatch T[11] != "a"
    j=0
            mismatch T[11] != "n"

Поскольку один студент указал в лекции, один переход в этом автомате, который не может быть ясен - тот от j=4 до j=0. Вообще, должен быть переход от j=m до небольшого количества меньшего значения j, который должен случиться на любом символе (нет больше пар, чтобы проверить перед созданием этого перехода). Если мы хотим найти все возникновения образца, мы должны быть способны найти возникновение, даже если это накладывается на другой. Так например, если образцом был "nana", мы должны найти оба возникновения этого в тексте "nanana". Так что переход от j=m должен идти в следующую самую длинную позицию, которая может соответствовать, который является просто j=overlap (pattern,pattern). В этом перекрытии случая{регистра} ("nano", "nano") пуст (все суффиксы "nano" используют символ "o", и никакой префикс не делает), так что мы идем в j=0.

Дополнительная версия KMП

Автомат выше может быть оттранслирован назад в псевдокод, смотря немного отличен от псевдокода, который мы видели прежде, но выполнение тех же самых сравнений.

KMП, версия 2:

    j = 0;
    for (i = 0; i < n; i++)
    for (;;) {      // loop until break
        if (T[i] == P[j]) { // matches?
        j++;        // yes, move on to next state
        if (j == m) {   // maybe that was the last state
            found a match;
            j = overlap[j];
        }
        break;
        } else if (j == 0) break;   // no match in state j=0, give up
        else j = overlap[j];    // try shorter partial match
    }

    while (x != empty) {
    x = overlap(x,y);
    output x;
    }

    z = overlap(shorten(x),y)
    while (last char of x != y[length(z)])
    {
    if (z = empty) return overlap(x,y) = empty
    else z = overlap(z,y)
    }
    return overlap(x,y) = z

    overlap[0] = -1;
    for (int i = 0; pattern[i] != '\0'; i++) {
    overlap[i + 1] = overlap[i] + 1;
    while (overlap[i + 1] > 0 &&
           pattern[i] != pattern[overlap[i + 1] - 1])
        overlap[i + 1] = overlap[overlap[i + 1] - 1] + 1;
    }
    return overlap;