verify/yosupo/yosupo-zalgorithm.test.cpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• library/string/z-algorithm.hpp

Code

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

#include <bits/stdc++.h>
#include "../../library/string/z-algorithm.hpp"

using namespace std;

int main() {
	string s;
	cin >> s;
	auto a = z_algorithm(s);
	for (int x : a) {
		cout << x << ' ';
	}
	cout << '\n';
	return 0;
}

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

#include <bits/stdc++.h>

template <class C> std::vector<int> z_algorithm(C s) {
	int n = (int)s.size();
	std::vector<int> a(n);
	a[0] = n;
	int i = 1, j = 0;
	while (i < n) {
		while (i + j < n && s[j] == s[i + j]) ++j;
		a[i] = j;
		if (j == 0) {
			++i;
			continue;
		}
		int k = 1;
		while (i + k < n && k + a[k] < j) a[i + k] = a[k], ++k;
		i += k;
		j -= k;
	}
	return a;
}

using namespace std;

int main() {
	string s;
	cin >> s;
	auto a = z_algorithm(s);
	for (int x : a) {
		cout << x << ' ';
	}
	cout << '\n';
	return 0;
}

Back to top page