花非花 (manacher算法)

登录—专业IT笔试面试备考平台_牛客网

给一个数组，问从每个i往后有多少回文串以i为左端点。

考虑manacher，用p数组做差分，对每一个最长的回文串的左端点加一，右端点减一，跑一遍即可。

#include
using namespace std;
#define int long long
#define ll long long
#define inf 1e14
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=2e6+10;
const int mod=1e9+7;
int n,m,a[maxn],b[maxn],p[maxn],cnt,res[maxn];
void init(){
	b[cnt]=-1;             
	for(int i=1;i<=n;i++) b[++cnt]=a[i],b[++cnt]=-2;
	b[++cnt]=-3;
}
void manacher(){
	int mr=0,mid=0;
	for (int i=1;i<=cnt;i++){
		if (imr){
			mr=i+p[i];
			mid=i;
		}
	}
}
//p[]代表以i为中心的字符串最大长度。 
signed main(){
	fast 
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	init();
	manacher();
	for (int i=1;i<=cnt;i++){
	    int l=i-(p[i]-1);
	    res[l]++,res[i+1]--;
	}
	int cur=0;
	for(int i=1;i<=cnt;i++){
	    cur+=res[i];
	    if(b[i]>0) printf("%d ",cur);
	}
}