Manacher's Algorithm(最長回文) (string/manacher.cpp)

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

なにこれ

連続部分文字列の最長回文の半径を求める．

関数

文字列 S の連続部分文字列のそれぞれの中心について，最長の回文の半径を格納する配列 v を返す．

• manacher(S)：i 文字目を中心とする最長の回文の半径を v[i] に格納する．
• manacher_even(S)：i 文字目を中心とする最長の回文の半径を v[2*i] に，i 文字目と i+1 文字目の境を中心とする最長の回文の半径を v[2*i+1] に格納する．

計算量

• $O(|S|)$

Verified with

• test/yosupo_enumerate_palindromes.cpp

Code

#pragma once

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

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

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

	return res;
}

vector<int> manacher_even(const string &S) {
	string S2;
	for(const char &c : S) (S2 += c) += '$';
	S2.pop_back();

	vector<int> res = manacher(S2);
	for(int i = 0; i < S.length() - 1; i++) {
		++res[i + i] >>= 1;
		res[i + i + 1] >>= 1;
	}
	++res[res.size() - 1] >>= 1;

	return res;
}

#line 2 "string/manacher.cpp"

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

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

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

	return res;
}

vector<int> manacher_even(const string &S) {
	string S2;
	for(const char &c : S) (S2 += c) += '$';
	S2.pop_back();

	vector<int> res = manacher(S2);
	for(int i = 0; i < S.length() - 1; i++) {
		++res[i + i] >>= 1;
		res[i + i + 1] >>= 1;
	}
	++res[res.size() - 1] >>= 1;

	return res;
}

Back to top page