Manacher's Algorithm
(content/string/manacher.h)

• View this file on GitHub
• Last update: 2024-02-01 17:09:56-05:00

Returns two vectors p1 and p2. p1[i]*2-1 is the length of the palindrome centered at index i of the string. p2[i]*2 is the length of the palindrome centered around the midpoint between indices i-1 and i in the string. This means that p2[0] is a dummy.

Depends on

• My starter code (content/utils/template.h)

Verified with

• tests/manacher.test.cpp

Code

#pragma once
#include "../utils/template.h"

/**
 * @brief Manacher's Algorithm
 * @docs docs/manacher.md
 */
 
pair<vector<int>, vector<int>> manacher(string s){
	s = "@"+s+"#";
	int n = (int)size(s);
	vector<int> p1(n), p2(n); //radii of palindromes (1 odd, 2 even length)
	
	for(int i = 1, mx = 0, p = 0; i < n-1; i++){
		p1[i] = (i >= mx) ? 1 : min(mx-i, p1[p*2-i]);
		while(s[i-p1[i]] == s[i+p1[i]])
			p1[i]++;
		if(i+p1[i] > mx)
			mx = i+p1[i], p = i;
	}
	for(int i = 1, mx = 0, p = 0; i < n-1; i++){
		p2[i] = (i >= mx) ? 0 : min(mx-i, p2[p*2-i+2]);
		while(s[i-p2[i]-1] == s[i+p2[i]])
			p2[i]++;
		if(i+p2[i] > mx)
			mx = i+p2[i], p = i-1;
	}
	p1.erase(p1.begin()); p2.erase(p2.begin());
	p1.pop_back(); p2.pop_back();
	return {p1, p2};
}

#line 1 "content/utils/template.h"
/**
 * @brief My starter code
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end());

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#line 3 "content/string/manacher.h"

/**
 * @brief Manacher's Algorithm
 * @docs docs/manacher.md
 */
 
pair<vector<int>, vector<int>> manacher(string s){
	s = "@"+s+"#";
	int n = (int)size(s);
	vector<int> p1(n), p2(n); //radii of palindromes (1 odd, 2 even length)
	
	for(int i = 1, mx = 0, p = 0; i < n-1; i++){
		p1[i] = (i >= mx) ? 1 : min(mx-i, p1[p*2-i]);
		while(s[i-p1[i]] == s[i+p1[i]])
			p1[i]++;
		if(i+p1[i] > mx)
			mx = i+p1[i], p = i;
	}
	for(int i = 1, mx = 0, p = 0; i < n-1; i++){
		p2[i] = (i >= mx) ? 0 : min(mx-i, p2[p*2-i+2]);
		while(s[i-p2[i]-1] == s[i+p2[i]])
			p2[i]++;
		if(i+p2[i] > mx)
			mx = i+p2[i], p = i-1;
	}
	p1.erase(p1.begin()); p2.erase(p2.begin());
	p1.pop_back(); p2.pop_back();
	return {p1, p2};
}

Back to top page