Z Algorithm
(library/string/z-algorithm.hpp)

• View this file on GitHub
• Last update: 2023-07-20 17:15:06+08:00
• Include: #include "library/string/z-algorithm.hpp"

$z[i]$ 為 $s[0, n)$ 和 $s[i, n)$ 最長共同前綴 (LCP) 的長度。

使用方法

string s = "ababacaca";
vector<int> z = z_algorithm(s); // 0 0 3 0 1 0 1 0 1

時間複雜度：$O(n)$

References

Atcoder Library document

Verified with

• test/string/z-algorithm/yosupo-Z-Algorithm.test.cpp

Code

#pragma once
#include <vector>
#include <cstring>
#include <algorithm>
#include <numeric>

namespace felix {

template<class T>
std::vector<int> z_algorithm(const std::vector<T>& a) {
	int n = a.size();
	std::vector<int> z(n);
	for(int i = 1, j = 0; i < n; ++i) {
		if(i <= j + z[j]) {
			z[i] = std::min(z[i - j], j + z[j] - i);
		}
		while(i + z[i] < n && a[i + z[i]] == a[z[i]]) {
			z[i]++;
		}
		if(i + z[i] > j + z[j]) {
			j = i;
		}
	}
	return z;
}

std::vector<int> z_algorithm(const std::string& s) {
	return z_algorithm(std::vector<int>(s.begin(), s.end()));
}

} // namespace felix

#line 2 "library/string/z-algorithm.hpp"
#include <vector>
#include <cstring>
#include <algorithm>
#include <numeric>

namespace felix {

template<class T>
std::vector<int> z_algorithm(const std::vector<T>& a) {
	int n = a.size();
	std::vector<int> z(n);
	for(int i = 1, j = 0; i < n; ++i) {
		if(i <= j + z[j]) {
			z[i] = std::min(z[i - j], j + z[j] - i);
		}
		while(i + z[i] < n && a[i + z[i]] == a[z[i]]) {
			z[i]++;
		}
		if(i + z[i] > j + z[j]) {
			j = i;
		}
	}
	return z;
}

std::vector<int> z_algorithm(const std::string& s) {
	return z_algorithm(std::vector<int>(s.begin(), s.end()));
}

} // namespace felix

Back to top page