Z-Function

Z-Function (หรือ Z-Array) เป็น algorithm ที่คำนวณ array $z$ โดยที่ $z[i]$ = ความยาวของ substring ที่ยาวที่สุดเริ่มจาก $s[i]$ ที่เป็น prefix ของ $s$

นิยาม

สำหรับ string $s$ ความยาว $n$:

$$z[i] = \max\{k : s[0..k-1] = s[i..i+k-1]\}$$

โดยที่ $z[0] = 0$ (หรือบางที่นิยามเป็น $n$)

ตัวอย่าง

String: "aabxaab"

i	s[i..]	z[i]	Explanation
0	aabxaab	0	(undefined/0)
1	abxaab	1	”a” = s[0]
2	bxaab	0	”b” != “a”
3	xaab	0	”x” != “a”
4	aab	3	”aab” = s[0..2]
5	ab	2	”ab” = s[0..1]
6	b	0	”b” != “a”

Algorithm

ใช้ concept ของ Z-Box คือ interval $[l, r]$ ที่ $s[l..r]$ = prefix ของ $s$

vector<int> zFunction(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    
    int l = 0, r = 0;  // Z-box [l, r]
    
    for (int i = 1; i < n; i++) {
        if (i < r) {
            // ใช้ค่าที่คำนวณไว้แล้ว
            z[i] = min(r - i, z[i - l]);
        }
        
        // Extend z[i] ด้วย naive comparison
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        
        // Update Z-box
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    
    return z;
}

Visualization

s = "aabxaab"
    0123456

i=1: s[1..] = "abxaab"
     Compare with s[0..] = "aabxaab"
     "a" matches, "b" != "a"
     z[1] = 1

i=4: s[4..] = "aab"
     Compare with s[0..] = "aab..."
     "aab" matches
     z[4] = 3

ประยุกต์ใช้งาน

1. Pattern Matching

ต่อ pattern กับ text: pattern + "$" + text

vector<int> zMatch(const string& text, const string& pattern) {
    string combined = pattern + "$" + text;
    vector<int> z = zFunction(combined);
    
    vector<int> matches;
    int m = pattern.size();
    
    for (int i = m + 1; i < combined.size(); i++) {
        if (z[i] == m) {
            matches.push_back(i - m - 1);
        }
    }
    
    return matches;
}

2. หา Period ของ String

int findSmallestPeriod(const string& s) {
    vector<int> z = zFunction(s);
    int n = s.size();
    
    for (int p = 1; p < n; p++) {
        // p เป็น period ถ้า z[p] = n - p
        if (z[p] == n - p && n % p == 0) {
            return p;
        }
    }
    
    return n;
}

3. นับ Distinct Substrings

long long countDistinctSubstrings(const string& s) {
    string current = "";
    long long total = 0;
    
    for (char c : s) {
        current = c + current;  // prepend
        vector<int> z = zFunction(current);
        
        int maxZ = 0;
        for (int i = 1; i < z.size(); i++) {
            maxZ = max(maxZ, z[i]);
        }
        
        total += current.size() - maxZ;
    }
    
    return total;
}

4. String Compression

หา representation สั้นที่สุดของ string ที่เป็นการซ้ำของ pattern

string compress(const string& s) {
    vector<int> z = zFunction(s);
    int n = s.size();
    
    for (int len = 1; len <= n; len++) {
        if (n % len == 0) {
            bool valid = true;
            for (int i = len; i < n; i += len) {
                if (z[i] < len && z[i] != n - i) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return s.substr(0, len) + " x " + to_string(n / len);
            }
        }
    }
    
    return s;
}

เปรียบเทียบ Z-Function กับ KMP

Aspect	Z-Function	KMP (Prefix Function)
Definition	Match with prefix from position i	Longest proper prefix = suffix
Value at i	Length of match starting at i	Length of matching prefix-suffix
Direction	Forward matching	Backward reference
Use case	Pattern at start	Pattern at end of current

Complexity

Operation	Time	Space
Build Z-array	$O(n)$	$O(n)$
Pattern search	$O(n + m)$	$O(n + m)$

Tips

1. เลือกใช้ Z หรือ KMP - ทั้งสองทำได้คล้ายกัน แต่บางปัญหาอาจง่ายกว่าด้วยอันใดอันหนึ่ง
2. Sentinel character - ใช้ตัวคั่นที่ไม่อยู่ใน alphabet
3. Z-box optimization - ทำให้ algorithm เป็น linear time