Почему алгоритм KMP (Кнута-Морриса-Пратта) использует length = prefixTable[length - 1] вместо просто length = length - 1 в следующем коде? Я в замешательстве, потому что изначально думал, что оба задания дадут одинаковый результат. Я понимаю, что ошибаюсь, но не знаю, где я ошибся. Может ли кто-нибудь объяснить эту разницу на примерах?
private int[] buildPrefixTable(String s) {
int[] prefixTable = new int[s.length()];
int length = 0;
for (int i = 1; i < s.length(); i++) {
while (length > 0 && s.charAt(i) != s.charAt(length)) {
length = prefixTable[length - 1];
}
if (s.charAt(i) == s.charAt(length)) {
length++;
}
prefixTable = length;
}
return prefixTable;
}
Подробнее здесь: https://stackoverflow.com/questions/790 ... ength-1-in
