mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

Z Algorithm
(string/z_algorithm.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "string/z_algorithm.hpp"

Z Algorithm

使い方

• vector<int> z_algorithm(string s) : 文字列 $S$ のと、 $S$ の $i$ 文字目以降の部分文字列との高さ配列を構築する $(O\lvert S\rvert)$

概要

参考

Required by

• verify/atcoder/abc/150/f.___test.cpp

Verified with

• verify/yosupo/zalgorithm.test.cpp

Code

#pragma once

#include<vector>

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

#line 2 "string/z_algorithm.hpp"

#include<vector>

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

Back to top page