This documentation is automatically generated by competitive-verifier/competitive-verifier
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
// clang-format on
#include <iostream>
#include <string>
#include "../../string/z-algorithm.hpp"
using namespace std;
int main() {
string s;
cin >> s;
auto z = ZAlgorithm(s).get();
for (int i = 0; i < static_cast<int>(z.size()); i++) {
if (i > 0) cout << " ";
cout << z[i];
}
cout << "\n";
}
#line 1 "test/verify/yosupo-zalgorithm.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
// clang-format on
#include <iostream>
#include <string>
#line 1 "string/z-algorithm.hpp"
/**
* @brief Z Algorithm
* @see https://heno239.hatenablog.com/entry/2020/07/07/140651
*
*/
#line 7 "string/z-algorithm.hpp"
#include <queue>
#include <vector>
template <typename T = char>
struct ZAlgorithm {
private:
std::vector<T> s;
std::vector<int> deleted;
std::vector<std::vector<int> > delete_hist;
std::vector<int> z;
std::queue<int> cur;
public:
ZAlgorithm() : delete_hist{{}} {}
template <typename S>
ZAlgorithm(const S& s) : ZAlgorithm() {
for (auto& c : s) add(c);
}
void add(const T& c) {
s.emplace_back(c);
delete_hist.emplace_back();
deleted.emplace_back(0);
z.emplace_back(0);
z[0]++;
int len = (int)s.size();
if (len == 1) return;
if (s[0] == c)
cur.emplace(len - 1);
else
deleted[len - 1] = 1;
auto set = [&](int t, int len) {
deleted[t] = 1;
delete_hist[len].emplace_back(t);
z[t] = len - t - 1;
};
while (not cur.empty()) {
int t = cur.front();
if (deleted[t]) {
cur.pop();
} else if (s[len - t - 1] == s.back()) {
break;
} else {
set(t, len);
cur.pop();
}
}
if (not cur.empty()) {
int t = cur.front();
for (auto& p : delete_hist[len - t]) {
set(p + t, len);
}
}
}
int get(int k) const { return deleted[k] ? z[k] : (int)s.size() - k; }
int operator[](int k) const { return get(k); }
std::vector<int> get() {
std::vector<int> ret(s.size());
for (int i = 0; i < (int)s.size(); i++) {
ret[i] = get(i);
}
return ret;
}
};
#line 9 "test/verify/yosupo-zalgorithm.test.cpp"
using namespace std;
int main() {
string s;
cin >> s;
auto z = ZAlgorithm(s).get();
for (int i = 0; i < static_cast<int>(z.size()); i++) {
if (i > 0) cout << " ";
cout << z[i];
}
cout << "\n";
}
| Env | Name | Status | Elapsed | Memory |
|---|---|---|---|---|
| g++ | all_same_00 |
|
50 ms | 25 MB |
| g++ | all_same_01 |
|
49 ms | 25 MB |
| g++ | all_same_02 |
|
48 ms | 25 MB |
| g++ | all_same_03 |
|
55 ms | 25 MB |
| g++ | all_same_04 |
|
50 ms | 25 MB |
| g++ | binary_carry_00 |
|
50 ms | 26 MB |
| g++ | binary_carry_01 |
|
46 ms | 26 MB |
| g++ | example_00 |
|
2 ms | 4 MB |
| g++ | example_01 |
|
2 ms | 4 MB |
| g++ | example_02 |
|
2 ms | 4 MB |
| g++ | example_03 |
|
2 ms | 4 MB |
| g++ | fib_str_00 |
|
48 ms | 27 MB |
| g++ | fib_str_01 |
|
36 ms | 20 MB |
| g++ | fib_str_02 |
|
37 ms | 20 MB |
| g++ | fib_str_03 |
|
38 ms | 20 MB |
| g++ | fib_str_04 |
|
46 ms | 25 MB |
| g++ | hack606_00 |
|
2 ms | 4 MB |
| g++ | max_random_00 |
|
46 ms | 24 MB |
| g++ | max_random_01 |
|
44 ms | 24 MB |
| g++ | random_00 |
|
38 ms | 20 MB |
| g++ | random_01 |
|
42 ms | 23 MB |
| g++ | random_02 |
|
7 ms | 6 MB |
| g++ | random_03 |
|
38 ms | 21 MB |
| g++ | random_04 |
|
29 ms | 20 MB |
| g++ | random_05 |
|
31 ms | 20 MB |
| g++ | random_06 |
|
44 ms | 22 MB |
| g++ | random_07 |
|
11 ms | 8 MB |
| g++ | random_08 |
|
29 ms | 20 MB |
| g++ | random_09 |
|
11 ms | 8 MB |
| clang++ | all_same_00 |
|
50 ms | 25 MB |
| clang++ | all_same_01 |
|
52 ms | 25 MB |
| clang++ | all_same_02 |
|
51 ms | 25 MB |
| clang++ | all_same_03 |
|
54 ms | 25 MB |
| clang++ | all_same_04 |
|
49 ms | 25 MB |
| clang++ | binary_carry_00 |
|
49 ms | 26 MB |
| clang++ | binary_carry_01 |
|
47 ms | 26 MB |
| clang++ | example_00 |
|
2 ms | 4 MB |
| clang++ | example_01 |
|
2 ms | 3 MB |
| clang++ | example_02 |
|
2 ms | 4 MB |
| clang++ | example_03 |
|
2 ms | 3 MB |
| clang++ | fib_str_00 |
|
48 ms | 26 MB |
| clang++ | fib_str_01 |
|
36 ms | 20 MB |
| clang++ | fib_str_02 |
|
35 ms | 20 MB |
| clang++ | fib_str_03 |
|
33 ms | 20 MB |
| clang++ | fib_str_04 |
|
47 ms | 25 MB |
| clang++ | hack606_00 |
|
2 ms | 4 MB |
| clang++ | max_random_00 |
|
45 ms | 24 MB |
| clang++ | max_random_01 |
|
46 ms | 24 MB |
| clang++ | random_00 |
|
39 ms | 20 MB |
| clang++ | random_01 |
|
44 ms | 22 MB |
| clang++ | random_02 |
|
7 ms | 6 MB |
| clang++ | random_03 |
|
40 ms | 21 MB |
| clang++ | random_04 |
|
29 ms | 20 MB |
| clang++ | random_05 |
|
32 ms | 20 MB |
| clang++ | random_06 |
|
42 ms | 22 MB |
| clang++ | random_07 |
|
10 ms | 8 MB |
| clang++ | random_08 |
|
28 ms | 20 MB |
| clang++ | random_09 |
|
12 ms | 8 MB |