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

• View this file on GitHub
• Last update: 2023-07-20 17:15:06+08:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

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

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <iostream>

#include "../../../library/string/z-algorithm.hpp"

using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> s;
	auto z = z_algorithm(s);
	z[0] = (int) s.size();
	for(int i = 0; i < (int) z.size(); i++) {
		cout << z[i] << " \n"[i == (int) z.size() - 1];
	}
	return 0;
}

#line 1 "test/string/z-algorithm/yosupo-Z-Algorithm.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <iostream>

#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
#line 5 "test/string/z-algorithm/yosupo-Z-Algorithm.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> s;
	auto z = z_algorithm(s);
	z[0] = (int) s.size();
	for(int i = 0; i < (int) z.size(); i++) {
		cout << z[i] << " \n"[i == (int) z.size() - 1];
	}
	return 0;
}

Back to top page