Guest User

Z-function

a guest
Apr 25th, 2025
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function getZ(string) {
  2.     const Z = new Array(string.length).fill(0);
  3.     const lastIndex = string.length - 1; // сократить строку в while
  4.     let l = 0, r = 0;
  5.     for (let i = 1; i <= string.length - 1; i++) {
  6.         // Используем уже собранную информацию, чтобы вычислить значения z для уже посещенных элементов.
  7.         if (i <= r)
  8.             Z[i] = Math.min(r - i + 1, Z[i - l]);
  9.  
  10.         while (
  11.         i + Z[i] <= lastIndex
  12.         && string[Z[i]] == string[i + Z[i]])
  13.             Z[i]++;
  14.        
  15.         // обновляем значения r и l, если мы ушли вправо дальше текущей r
  16.         if (i + Z[i] - 1 > r) {
  17.             r = i + Z[i] - 1;
  18.             l = i;
  19.         }
  20.     }
  21.     return Z;
  22. }
Add Comment
Please, Sign In to add comment