src/string/z_algorithm.hpp

• View this file on GitHub
• Last update: 2022-12-22 01:59:18+09:00
• Include: #include "src/string/z_algorithm.hpp"

Verified with

• test/yosupo_judge/zalgorithm.test.cpp

Code

#pragma once

#include <bits/stdc++.h>
using namespace std;

template <typename T = int> vector<T> z_algorithm(string s) {
  int n = s.size();
  vector<T> res(n, 0);
  res[0] = n;
  int i = 1, j = 0;
  while (i < n) {
    while (i + j < n && s[j] == s[i + j]) {
      ++j;
    }
    res[i] = j;
    if (j == 0) {
      ++i;
      continue;
    }
    int k = 1;
    while (i + k < n && k + res[k] < j) {
      res[i + k] = res[k];
      ++k;
    }
    i += k;
    j -= k;
  }
  return res;
}

#line 2 "src/string/z_algorithm.hpp"

#include <bits/stdc++.h>
using namespace std;

template <typename T = int> vector<T> z_algorithm(string s) {
  int n = s.size();
  vector<T> res(n, 0);
  res[0] = n;
  int i = 1, j = 0;
  while (i < n) {
    while (i + j < n && s[j] == s[i + j]) {
      ++j;
    }
    res[i] = j;
    if (j == 0) {
      ++i;
      continue;
    }
    int k = 1;
    while (i + k < n && k + res[k] < j) {
      res[i + k] = res[k];
      ++k;
    }
    i += k;
    j -= k;
  }
  return res;
}

Back to top page