Z Algorithm
(content/string/z_algorithm.h)

• View this file on GitHub
• Last update: 2024-02-01 17:09:56-05:00

z[i] = length of the longest common prefix between s and s[i, end]. z[0] is defined to be 0.

Depends on

• My starter code (content/utils/template.h)

Verified with

• tests/z_algorithm.test.cpp

Code

#pragma once
#include "../utils/template.h"

/**
 * @brief Z Algorithm
 * @docs docs/z_algorithm.md
 */

vector<int> zed(string s){
	int n = (int)size(s);
	vector<int> z(n);
	for(int i = 1, l = 0, r = 0; i < n; i++){
		if(i <= r)
			z[i] = min(r-i+1, z[i-l]);
		while(i+z[i] < n and s[z[i]] == s[i+z[i]])
			z[i]++;
		if(i+z[i]-1 > r)
			l = i, r = i+z[i]-1;
	}
	return z;
}

#line 1 "content/utils/template.h"
/**
 * @brief My starter code
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end());

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#line 3 "content/string/z_algorithm.h"

/**
 * @brief Z Algorithm
 * @docs docs/z_algorithm.md
 */

vector<int> zed(string s){
	int n = (int)size(s);
	vector<int> z(n);
	for(int i = 1, l = 0, r = 0; i < n; i++){
		if(i <= r)
			z[i] = min(r-i+1, z[i-l]);
		while(i+z[i] < n and s[z[i]] == s[i+z[i]])
			z[i]++;
		if(i+z[i]-1 > r)
			l = i, r = i+z[i]-1;
	}
	return z;
}

Back to top page