Z algorithm（補助部品）

components/z_algorithm.hpp · GitHub で見る

共通ページ

一致長を計算する関数を受け取り、Z 配列や接頭辞との一致長を列挙する内部部品です。

#include "lib/components/z_algorithm.hpp"
#include <string>
#include <vector>

std::string s = "ababa";
std::vector<int> z(s.size());
sequence_match_detail::z_table(int(s.size()), z.data(), [&](int i, int j, int limit) {
	int k = 0;
	while (k < limit && s[i + k] == s[j + k]) ++k;
	return k;
}); // z = {5,0,3,0,1}

操作	内容・返り値	計算量
sequence_match_detail::z_table(n,z,match)	長さ n の列の Z 配列を z に書き込む。z[0]=n	\(O(n)\) 回の要素比較
sequence_match_detail::prefix_matches(n,m,z,match,emit)	対象の n 個の開始位置について、長さ m の接頭辞との一致長を emit(i,length) に渡す	\(O(n+m)\) 回の要素比較

match(i,j,limit) は、比較する 2 列の位置 i,j から高々 limit 要素の一致長を返します。z_table は同じ列同士、prefix_matches は接頭辞の列と対象の列を比較する関数を渡します。

z_table は n>=0 とし、長さ n の書き込み領域を用意します。n=0 では読み書きしません。prefix_matches は m>0 とし、長さ m の接頭辞の Z 配列と、各開始位置から m 要素まで比較できる対象を渡します。

要素比較を \(O(1)\) として、Z 配列は時間 \(O(n)\)、接頭辞一致の列挙は時間 \(O(n+m)\)、出力を除く追加空間はいずれも \(O(1)\) です。

検証コード

• test/run_enumerate.test.cpp
• test/z_algorithm.test.cpp

コード

#ifndef Z_ALGORITHM_HPP
#define Z_ALGORITHM_HPP

namespace sequence_match_detail {
template <class F>
void z_table(int n, int *z, F match) {
	if (!n) return;
	z[0] = n;
	for (int i = 1, base = 0, end = 0; i < n; ++i) {
		int length = 0;
		if (i < end) {
			length = z[i - base];
			if (length < end - i) {
				z[i] = length;
				continue;
			}
			length = end - i;
		}
		length += match(length, i + length, n - i - length);
		z[i] = length;
		if (i + length > end) base = i, end = i + length;
	}
}

template <class F, class Emit>
void prefix_matches(int n, int m, const int *z, F match, Emit emit) {
	for (int i = 0, base = 0, end = 0; i < n; ++i) {
		int length = 0;
		if (i < end) {
			length = z[i - base];
			if (length < end - i) {
				emit(i, length);
				continue;
			}
			length = end - i;
		}
		length += match(length, i + length, m - length);
		if (i + length > end) base = i, end = i + length;
		emit(i, length);
	}
}
}

#endif

Back to top page