Блог пользователя dlda

Непонятный рядок в префикс-функции
Автор dlda, 10 лет назад, По-русски

Не могу понять почему эта строка j = pi[j-1]; в префикс-функции дает нам правильную позицию.

Об'ясните пожалуста почему это работает =)

Код с e-maxx.ru:

vector<int> prefix_function (string s) {
	int n = (int) s.length();
	vector<int> pi (n);
	for (int i=1; i<n; ++i) {
		int j = pi[i-1];
		while (j > 0 && s[i] != s[j])
			j = pi[j-1];
		if (s[i] == s[j])  ++j;
		pi[i] = j;
	}
	return pi;
}
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Ну потому что префикс-функция — это длина, а строка нумеруется с нуля. В 1-индексации было бы pi[pi[j]].
Или проблема с пониманием алгоритма?

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Так это ясно... Почему мы переходим именно в оптимальную позицию?

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    почему мы не пропустим ничего важного между j и p[j — 1] ?

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

      Пусть оказалось, что s[i+1] != s[j]. Тогда нам надо попытаться попробовать подстроку меньшей длины. В целях оптимизации хотелось бы сразу перейти к такой (наибольшей) длине j < pi[i], что по-прежнему выполняется префикс-свойство в позиции i. Фактически мы имеем две одинаковые строки s[0] .. s[j — 1] и s[i — j + 1]...s[i] и ето используем. Мы используем теперь найдено предварительно значение префикс функции для строки s[0] .. s[j — 1]

      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

Вот я, кстати, тоже думаю, что правильнее вот так писать:

     for(int i = 1; i < n; i++)
     {
         p[i] = p[i - 1];
         while(p[i] && s[i] != s[p[i]]) p[i] = p[p[i] - 1];
         if(s[i] == s[p[i]]) p[i]++;
     }

А то понапридумывали тут своих промежуточных переменных...

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

too late but maybe this helps. https://www.youtube.com/watch?v=nJbNe0Yzjhw

→ Ответить