test/string/z_algorithm.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Code

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

int main() {
  string s; cin>>s;
  auto z = z_algorithm(s.begin(), s.end());
  for (int i = 0; i < (int) s.size(); i++)
    cout << z[i] << ' ';
  cout << endl;
}

#line 1 "test/string/z_algorithm.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#line 2 "include/mtl/string/z_algorithm.hpp"
#include <vector>
#include <iterator>

template<typename It>
std::vector<int> z_algorithm(It begin, It end) {
  using trait = std::iterator_traits<It>;
  static_assert(std::is_base_of<std::random_access_iterator_tag, typename trait::iterator_category>::value, "");
  int n = end - begin;
  std::vector<int> z(n);
  z[0] = n;
  int i = 1, j = 0;
  while (i < n) {
    while (i+j < n and *(begin + i+j) == *(begin + j))
      ++j;
    if (j == 0) {
      ++i;
      continue;
    }
    z[i] = j;
    int k = 1;
    while (k < j and k + z[k] < j) {
      z[i+k] = z[k];
      ++k;
    }
    i += k;
    j -= k;
  }
  return z;
}
#line 3 "test/string/z_algorithm.test.cpp"
#include <iostream>
using namespace std;

int main() {
  string s; cin>>s;
  auto z = z_algorithm(s.begin(), s.end());
  for (int i = 0; i < (int) s.size(); i++)
    cout << z[i] << ' ';
  cout << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	41 ms	6 MB
g++	all_same_01	AC	43 ms	6 MB
g++	all_same_02	AC	42 ms	6 MB
g++	all_same_03	AC	41 ms	6 MB
g++	all_same_04	AC	42 ms	6 MB
g++	binary_carry_00	AC	37 ms	6 MB
g++	binary_carry_01	AC	37 ms	6 MB
g++	example_00	AC	6 ms	3 MB
g++	example_01	AC	5 ms	3 MB
g++	example_02	AC	5 ms	3 MB
g++	example_03	AC	5 ms	3 MB
g++	fib_str_00	AC	38 ms	6 MB
g++	fib_str_01	AC	30 ms	5 MB
g++	fib_str_02	AC	30 ms	5 MB
g++	fib_str_03	AC	27 ms	5 MB
g++	fib_str_04	AC	39 ms	6 MB
g++	hack606_00	AC	5 ms	3 MB
g++	max_random_00	AC	39 ms	6 MB
g++	max_random_01	AC	40 ms	6 MB
g++	random_00	AC	32 ms	5 MB
g++	random_01	AC	35 ms	6 MB
g++	random_02	AC	9 ms	4 MB
g++	random_03	AC	34 ms	5 MB
g++	random_04	AC	23 ms	5 MB
g++	random_05	AC	26 ms	5 MB
g++	random_06	AC	35 ms	6 MB
g++	random_07	AC	11 ms	4 MB
g++	random_08	AC	23 ms	5 MB
g++	random_09	AC	12 ms	4 MB
clang++	all_same_00	AC	36 ms	6 MB
clang++	all_same_01	AC	38 ms	6 MB
clang++	all_same_02	AC	46 ms	6 MB
clang++	all_same_03	AC	47 ms	6 MB
clang++	all_same_04	AC	46 ms	6 MB
clang++	binary_carry_00	AC	36 ms	6 MB
clang++	binary_carry_01	AC	35 ms	6 MB
clang++	example_00	AC	5 ms	3 MB
clang++	example_01	AC	5 ms	3 MB
clang++	example_02	AC	5 ms	3 MB
clang++	example_03	AC	5 ms	3 MB
clang++	fib_str_00	AC	33 ms	6 MB
clang++	fib_str_01	AC	26 ms	5 MB
clang++	fib_str_02	AC	25 ms	5 MB
clang++	fib_str_03	AC	24 ms	5 MB
clang++	fib_str_04	AC	33 ms	6 MB
clang++	hack606_00	AC	6 ms	3 MB
clang++	max_random_00	AC	34 ms	6 MB
clang++	max_random_01	AC	36 ms	6 MB
clang++	random_00	AC	27 ms	5 MB
clang++	random_01	AC	32 ms	6 MB
clang++	random_02	AC	8 ms	4 MB
clang++	random_03	AC	29 ms	5 MB
clang++	random_04	AC	21 ms	5 MB
clang++	random_05	AC	23 ms	5 MB
clang++	random_06	AC	30 ms	6 MB
clang++	random_07	AC	11 ms	4 MB
clang++	random_08	AC	20 ms	5 MB
clang++	random_09	AC	11 ms	4 MB

Back to top page