各要素について、その要素を中心とする最長回文の半径をもとめる (daylight/string/manacher.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/string/manacher.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)

Verified with

• test/yosupo/string/enumerate_palindromes.test.cpp

Code

#include "daylight/base.hpp"

/// @brief 各要素について、その要素を中心とする最長回文の半径をもとめる
/// @param S 対象の配列
/// @return ret[i]:i番目の要素を中心とする最長回文の半径
template<typename T>
vi manacher(vector<T>& S) {
	int N = SZ(S);
	int i = 0;
	int j = 0;
	vi ret(N);
	while(i < N) {
		while(i - j >= 0 && i + j < N
			  && S[i - j] == S[i + j])
			j++;
		ret[i] = j;
		int k = 1;
		while(i - k >= 0 && k + ret[i - k] < j) {
			ret[i + k] = ret[i - k];
			k++;
		}
		i += k;
		j -= k;
	}
	return ret;
}
/// @brief 各文字について、その文字を中心とする最長回文の半径をもとめる
/// @param S 対象の文字列
/// @return ret[i]:i文字目を中心とする最長回文の半径
vi manacher(string& S) {
	vector<char> v;
	for(auto c: S) {
		v.push_back(c);
	}
	return manacher(v);
}

/// @brief 2N-1個の場所(要素と、要素と要素の間)について、それを中心とする最長回文の半径
/// @param S 対象のvector
/// @return ret[i](長さ2N-1):左からi番目の場所を中心とする最長回文の半径
template<typename T>
vi ext_manacher(vector<T>& S, T split) {
	vector<T> v;
	int N = SZ(S);
	REP(i, N) {
		if(i != 0) v.push_back(split);
		v.push_back(S[i]);
	}
	auto ret = manacher(v);
	REP(i, 2 * N - 1) {
		if(i % 2 == 0) {
			ret[i] = (ret[i] + 1) / 2;
		} else {
			ret[i] = ret[i] / 2;
		}
	}
	return ret;
}
/// @brief 2N-1個の場所(文字と、文字と文字の間)について、それを中心とする最長回文の半径
/// @param S 対象の文字列
/// @return ret[i](長さ2N-1):左からi番目の場所を中心とする最長回文の半径
vi ext_manacher(string& S, char split = '$') {
	vector<char> v;
	for(auto c: S) {
		v.push_back(c);
	}
	return ext_manacher(v, split);
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page