PALINY - Palindrome dài nhất

Tác giả: skyvn97

Ngôn ngữ: C++

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
string s;
int manacher(const string &s) {	
	string t="^";	
	int c,r;	
	FORE(it,s) {
		assert(*it!='^' && *it!='#' && *it!='$');
		t.push_back('#');
		t.push_back(*it);
	}
	t+="#$";
	int n=t.size();	
	vector<int> p=vector<int>(n+7,0);
	c=0;
	r=0;
	FOR(i,1,n-1) {
		if (r>i) p[i]=min(r-i,p[2*c-i]);
		else p[i]=0;
		while (t[i+1+p[i]]==t[i-1-p[i]]) p[i]++;
		if (i+p[i]>r) {
			c=i;
			r=i+p[i];
		}		
	}
	int ret=0;
	FOR(i,1,n-1) ret=max(ret,p[i]);
	return (ret);
}
int main(void) {
	srand(time(NULL));
	ios::sync_with_stdio(rand()%2);
	cin >> s >> s;
	cout << manacher(s);
	return 0;
}

Download