mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

manachar
(string/manachar.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "string/manachar.hpp"

manachar

使い方

0-indexed で表す。

• vector<int>manachar(string s) : 文字列 $S$ の
  • 奇数番目 : $S_{i/2}, S_{i/2+1}$ の間を中心とした回文の半径
  • 偶数番目 : $S_{i/2}$ を中心とした回文の半径（自身を含む）
• を求めた長さ $2n-1$ の配列を返す $O(\lvert S \rvert)$

Verified with

• verify/yosupo/enumerate_palindromes.test.cpp

Code

#pragma once

#include<string>
#include<vector>

std::vector<int> manachar(std::string _s){
	std::string t = "";
	int n = (int)_s.size();
	for(int i = 0;i < n;i++){
		if(i)t += '#';
		t += _s[i];
	}
	n = (int)t.size();
	int i = 0, j = 0;
	std::vector<int> r(n);
	while(i < n){
		while(i-j >= 0 && i+j < n && t[i-j] == t[i+j]) j++;
		r[i] = j;
		int k = 1;
		while(i-k >= 0 && k+r[i-k] < j) r[i+k] = r[i-k], k++;
		i += k, j -= k;
	}
	for(int k = 0;k < n;k++){
		if(k&1)r[k] >>= 1;
		else r[k] = (r[k]+1) >> 1;
	}
	return r;
}

/*
int i = 0, j = 0;
while (i < S.size()) {
  while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
  R[i] = j;
  int k = 1;
  while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
  i += k; j -= k;
}
*/

#line 2 "string/manachar.hpp"

#include<string>
#include<vector>

std::vector<int> manachar(std::string _s){
	std::string t = "";
	int n = (int)_s.size();
	for(int i = 0;i < n;i++){
		if(i)t += '#';
		t += _s[i];
	}
	n = (int)t.size();
	int i = 0, j = 0;
	std::vector<int> r(n);
	while(i < n){
		while(i-j >= 0 && i+j < n && t[i-j] == t[i+j]) j++;
		r[i] = j;
		int k = 1;
		while(i-k >= 0 && k+r[i-k] < j) r[i+k] = r[i-k], k++;
		i += k, j -= k;
	}
	for(int k = 0;k < n;k++){
		if(k&1)r[k] >>= 1;
		else r[k] = (r[k]+1) >> 1;
	}
	return r;
}

/*
int i = 0, j = 0;
while (i < S.size()) {
  while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
  R[i] = j;
  int k = 1;
  while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
  i += k; j -= k;
}
*/

Back to top page