test/ZAlgotihm.test.cpp

• View this file on GitHub
• Last update: 2021-04-06 14:09:02+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• string/ZAlgorithm.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include "./../string/ZAlgorithm.cpp"
#include <iostream>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size();
	auto a = ZAlgorithm(s);
	for (int i = 0; i < n; ++i) {
		cout << a[i] << (i < n - 1 ? ' ' : '\n');
	}
}

#line 1 "test/ZAlgotihm.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#line 2 "string/ZAlgorithm.cpp"
#include <vector>

template <class T> std::vector<int> ZAlgorithm(const T& s) {
	if (s.size() == 0) {
		return {};
	}
	int n = s.size(), i = 1, j = 0;
	std::vector<int> result(n);
	result[0] = n;
	while (i < n) {
		while (i + j < n && s[j] == s[i + j]) j++;
		result[i] = j;
		if (j == 0) {
			i++;
			continue;
		}
		int k = 1;
		while (i + k < n && k + result[k] < j) {
			result[i + k] = result[k];
			k++;
		}
		i += k;
		j -= k;
	}
	return result;
}
#line 3 "test/ZAlgotihm.test.cpp"
#include <iostream>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size();
	auto a = ZAlgorithm(s);
	for (int i = 0; i < n; ++i) {
		cout << a[i] << (i < n - 1 ? ' ' : '\n');
	}
}

Back to top page