Почему / Как работает алгоритм самого длинного правильного префикса / суффикса? - PullRequest
Новая
       45

Почему / Как работает алгоритм самого длинного правильного префикса / суффикса?

1 голос
/ 25 марта 2020

Алгоритм LPS (самый длинный правильный префикс, который также является суффиксом) выглядит следующим образом: 

public static int[] constructLPSArray(String s) {
        int n = s.length();
        int[] arr = new int[n];
        int j = 0;
        for (int i = 1; i < n; ) {
            if (s.charAt(i) == s.charAt(j)) {
                arr[i] = j + 1;
                i++;
                j++;
            } else {
                if (j != 0) {
                    j = arr[j - 1];
                } else {
                    i++;
                }
            }
        }
        return arr;
    }

Часть if (s.charAt(i) == s.charAt(j)) выглядит четкой, но часть else неясна. Почему мы делаем: 

if (j != 0) {
  j = arr[j - 1];
} else {
  i++;
}

Более конкретно, почему j = arr[j - 1] работает? Или почему мы вообще это делаем? Как мы можем подтвердить правильность этого шага?

Пожалуйста, помогите !!

1 Ответ

1 голос
/ 26 марта 2020

Допустим, мы анализируем массив символов с i и j, расположенными так: 

a b a b x x a b a b ...
      ^           ^
      j           i

с arr, удерживая: 

0 0 1 2 0 0 1 2 3 4

т.е. длина самого длинного префикса / суффикса каждой подстроки s этой длины до i. Вы, вероятно, можете догадаться, как это было сгенерировано из остальной части алгоритма. Теперь, если следующий символ после i не соответствует следующему символу после j, 

a b a b x x a b a b a ...
        ^           ^
        j           i

, нам не нужно повторять сопоставление, потому что мы знаем самый длинный префикс / суффикс нашего предыдущего префикса / суффикса! При поиске arr[j - 1] получается 2 - поэтому мы по существу кэшировали информацию о том, что выделенные здесь части 

A B a b x x a b A B a ...
=== ^           === ^
    j               i

идентичны и их не нужно сравнивать снова!

...