Z-Algorithm(最長共通接頭辞) (string/z_algorithm.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-06 03:54:40+09:00

なにこれ

文字列 $S$ とその連続部分文字列 $S[i, |S|)$ の最長共通接頭辞の長さを求める．

関数

• z_algorithm(S)：S と S[i, |S|) の最長共通接頭辞の長さを v[i] とする配列 v を返す．

計算量

• $O(|S|)$

Verified with

• test/yosupo_zalgorithm.cpp
• test/yuki_0599.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

vector<int> z_algorithm(const string &S) {
	int N = S.length();
	vector<int> res(N, 0);

	for(int i = 1, c = 0; i < N; i++) {
		int l = i - c;
		if(i + res[l] < c + res[c]) {
			res[i] = res[l];
		}
		else {
			int l = max(c + res[c] - i, 0);
			while(i + l < N && S[l] == S[i + l]) l++;
			res[i] = l;
			c = i;
		}
	}

	res[0] = N;
	return res;
}

#line 2 "string/z_algorithm.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

vector<int> z_algorithm(const string &S) {
	int N = S.length();
	vector<int> res(N, 0);

	for(int i = 1, c = 0; i < N; i++) {
		int l = i - c;
		if(i + res[l] < c + res[c]) {
			res[i] = res[l];
		}
		else {
			int l = max(c + res[c] - i, 0);
			while(i + l < N && S[l] == S[i + l]) l++;
			res[i] = l;
			c = i;
		}
	}

	res[0] = N;
	return res;
}

Back to top page