题意:求最长回文串长度,要求回文串左边是非下降。
思路一:
先把连续的回文串,满足先上升再下降的序列处理出来,再对这部分序列做马拉车模板就可以了。
需要注意的是,由于他要的是非下降的序列,所以要注意等于的情况。
还需要注意的是,写马拉车的板子习惯用的是char。。但是char的上限是255,'0'+250会爆char。因为这个wa了好几天也没想出bug是什么。
思路二:
对马拉车算法进行修改,只要在判断回文的时候加入递增这个条件即可。
两个思路都实现了一遍。
#include<bits/stdc++.h> #define clr(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const int maxn=110010; int s[maxn<<1],ne[maxn<<1]; int p[maxn<<1],mx,maxx,n,T,a[maxn<<1],b[maxn],cnt; int init(int b[],int len){ int j=2; ne[0]='$',ne[1]='#'; for(int i=1;i<=len;i++) { ne[j++]=('0'+b[i]); ne[j++]='#'; } ne[j]='