На головну

Z-функція рядка і її обчислення

  1. GOSUB номер рядка або мітка
  2. Алгоритми виведення графічних примітивів. Пряме обчислення координат.
  3. Обчислення видимих ??координат світил ».
  4. обчислення виразів
  5. Обчислення подвійного інтеграла за допомогою повторного інтегрування
  6. Обчислення значень функції

Нехай дана рядок  довжини  . Тоді Z-функція ( "зет-функція") від цього рядка - це масив довжини ,  -ий елемент якого дорівнює найбільшому числу символів, починаючи з позиції  , Які збігаються з першими символами рядка .

Іншими словами,  - Це найбільший спільний префікс рядка  і її  -го суфікса.

vector z_function (string s) {

int n = (int) s.length ();

vector z (n);

for (int i = 1, l = 0, r = 0; i

if (i <= r)

z [i] = min (r-i + 1, z [i-l]);

while (i + z [i]

++ Z [i];

if (i + z [i] -1> r)

l = i, r = i + z [i] -1;

}

return z;

}

 



Теорема Піка. | Знаходження наідліннейшей зростаючої підпослідовності

Флойд-Уоршелл | Алгоритм пошуку компонент зв'язності в графі | Пошук точок зчленування | Алгоритм Куна знаходження найбільшого паросполучення в дводольному графі | Розширений Евклід | дискретного логарифмування | Знаходження найбільшою нульовий подматріци | Біноміальні коефіцієнти | числа Каталана | намиста |

© um.co.ua - учбові матеріали та реферати