Algoritmalar
en

Z-Algorithm

Strings O(n) O(n)

Computes, for every position, the length of the longest substring starting there that matches a prefix of the string — reusing a [l, r) window.

text
A100
A·1
B·2
X·3
A·4
A·5
Y·6
A·7
A·8
B·9
i=0l=0r=0
1/24

z[0] = n by definition.

Invariantz[i] is the length of the longest substring starting at i that matches a prefix of the text.

z-algorithm.c
void zArray(const char *s, int n, int z[]) {
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r)
            z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n &&
               s[z[i]] == s[i + z[i]])
            z[i]++;
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
}

How Z-Algorithm works

Z[i] = length of the longest substring starting at i that matches the string's own prefix. A maintained [l, r) match window lets each Z value start from a mirrored earlier one instead of zero.

When to use it

Pattern matching (search P#T), string periodicity, prefix-based similarity.