【BZOJ 3676】[Apio2014] 回文串


1. 10min 确定 SA + manacher
2. 1h 码完代码
3. 6h 调试代码,BZOJ仍然超时QAQ
4. UOJ上发现原题,提交,通过!
————————————————— 我是华丽丽的分割线,下面才是正文 ———————————————————
2.BZOJ数据太强,SA + manacher要T,不过UOJ可过(其实在manacher那里分类讨论的话,也是可以卡过的

#define LL long long
using namespace std;

const int MAXN = 1210000;

char BUF[MAXN],pat[MAXN];
int n,rep[MAXN],LEN[MAXN];
LL vout=1;

inline void init(){
	n = strlen(BUF+1);
	for (int i=1;i<=n;i++){
		pat[i*2-1] = 123;
		pat[i*2] = BUF[i];
	} n = n*2+1;
	pat[n]=123; LEN[1] = 0;
	for (int i=2;i<=n;i++)
		LEN[i] = LEN[i>>1]+1;

namespace Suffix_Array{
	#define SA Suffix_Array
	#define SIGMA_SIZE 30
	int sa[MAXN],bot[MAXN],t1[MAXN],t2[MAXN],*tmp,*rank;
	int m,height[MAXN];

	namespace Sparse_Table{
		#define ST Sparse_Table
		int mx[MAXN][17];

		inline void init(){
			for (int i=1;i<=n;i++)
				mx[i][0] = height[i];
			for (int i=1,len=1;len<=n;i++,len*=2){
				for (int j=1;j<=n;j++)
					mx[j][i] = min(mx[j][i-1],mx[j+len][i-1]);

		inline int query(int l, int r){
			int t=LEN[r-l+1];
			return min(mx[l][t],mx[r-(1<<t)+1][t]);

	inline void GetHeight(char *s){
		for (int i=1,t=0;i<=n;i++){
			if (t) t--;
			int p1 = i+t, p2 = sa[rank[i]-1]+t;
			while (s[p1++] == s[p2++]) t++;
			height[rank[i]] = t;
		pat[n+1]=125; pat[0]=124;

	inline void build(char *s){
		m = SIGMA_SIZE; tmp = t1; rank = t2;
		for (int i=1;i<=n;i++) bot[tmp[i]=s[i]-'a'+1]++;
		for (int i=2;i<m;i++) bot[i] += bot[i-1];
		for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
		rank[sa[1]] = m = 1;
		for (int i=2;i<=n;i++)
			if (s[sa[i]] != s[sa[i-1]]) rank[sa[i]] = ++m;
			else rank[sa[i]] = m;

		for (int k=1,T=0;k<=n;k*=2,T=0){
			for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
			for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k;
			for (int i=1;i<=m;i++) bot[i] = 0;
			for (int i=1;i<=n;i++) bot[rank[i]]++;
			for (int i=2;i<=m;i++) bot[i] += bot[i-1];
			for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];

			rank[sa[1]] = m = 1;
			for (int i=2;i<=n;i++)
				if (tmp[sa[i]]==tmp[sa[i-1]] && tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]] = m;
				else rank[sa[i]] = ++m;

			if (m >= n) break;


	inline int match_right(int s,int len){
		int l = 1, r = n-s,ret=1;
		while (l <= r){
			int mid = (l + r) / 2;
			if (ST::query(s+1,s+mid) >= len) ret = mid, l=mid+1;
			else r = mid-1;
		return ret;

	inline int match_left(int s,int len){
		int l = 1, r = s,ret=1;
		while (l <= r){
			int mid = (l + r) / 2;
			if (ST::query(s-mid+1,s) >= len) ret = mid, l=mid+1;
			else r = mid-1;
		return ret;

	inline int search(int s, int len){
		int ret = 1, pos = rank[s];
		if (height[pos] >= len && pos > 1) ret += match_left(pos,len);
		if (height[pos+1] >= len && pos < n) ret += match_right(pos,len);
		return ret;

inline void solve(int i){
	int beg = i-rep[i];
	int t = SA::search(beg,rep[i]*2+1);
	vout = max(vout, (LL)t*(LL)rep[i]);

inline void manacher(){
	int itr=0;
	for (int i=1;i<=n;i++){
		if (rep[itr]+itr > i) rep[i] = min(rep[itr*2-i],rep[itr]+itr-i);
		else rep[i] = 0;
		int p1 = i+rep[i], p2 = i-rep[i];
		while (pat[--p2]==pat[++p1])
			rep[i]++, solve(i);
		if (rep[i]+i > rep[itr]+itr) itr = i;

int main(){
	return 0;


#define LL long long
using namespace std;

const int MAXN = 300000+9;

char pat[MAXN];

namespace Palindromic_Tree{
	#define PAM Palindromic_Tree
	#define SIGMA_SIZE 26
	int ch[MAXN][SIGMA_SIZE],sz[MAXN],fail[MAXN];
	int n,cnt,last,len[MAXN];

	inline void init(){
		cnt = 1;
		fail[0] = fail[1] = 1;
		len[1] = -1;

	inline void expend(int pos, int c, char *s){
		int cur = last;
		while (s[pos-len[cur]-1] != s[pos]) cur = fail[cur];
		if (!ch[cur]){
			int w = ++cnt, k = fail[cur];
			len[w] = len[cur] + 2;
			while (s[pos-len[k]-1] != s[pos]) k = fail[k];
			fail[w] = ch[k]; ch[cur] = w;
		last = ch[cur];

	inline void build(char *s){
		n = strlen(s+1);
		for (int i=1;i<=n;i++)

	inline LL solve(){
		LL ret = 1;
		for (int i=cnt;i;i--){
			sz[fail[i]] += sz[i];
			ret = max(ret, (LL)len[i]*(LL)sz[i]);
		return ret;

int main(){
	return 0;

16 thoughts to “【BZOJ 3676】[Apio2014] 回文串”

  1. You actually make it seem so easy with your presentation but I find this topic to be really
    something which I think I would never understand. It seems too complex and extremely broad for me.
    I’m looking forward for your next post, I will try to get the
    hang of it!

  2. We are a gaggle of volunteers and starting a new scheme
    in our community. Your site offered us with helpful information to work on. You have performed an impressive job and our whole neighborhood will be
    thankful to you.

  3. Write more, thats all I have to say. Literally, it seems as
    though you relied on the video to make your point.
    You clearly know what youre talking about, why throw away your intelligence on just posting
    videos to your blog when you could be giving us something enlightening to read?

  4. I’m not sure why but this site is loading extremely
    slow for me. Is anyone else having this issue or is it a problem on my end?
    I’ll check back later and see if the problem still exists.

  5. I will right away seize your rss as I can’t to find your e-mail subscription link or newsletter service. Do you have any? Kindly let me recognise so that I could subscribe. Thanks.

  6. I like the valuable info you provide in your articles.
    I will bookmark your weblog and check again here frequently.
    I am quite sure I’ll learn many new stuff right here! Best of luck for the

  7. Undeniably consider that that you stated. Your favourite reason appeared to
    be at the net the simplest factor to keep in mind of. I say
    to you, I definitely get annoyed even as other folks consider issues that they just do not understand about.
    You controlled to hit the nail upon the highest and defined out the entire thing without having side-effects ,
    other folks can take a signal. Will likely be again to get
    more. Thank you

  8. Pretty section of content. I just stumbled upon your blog and in accession capital to claim that I acquire
    in fact loved account your blog posts. Anyway I’ll be subscribing to your augment or even I success you get right of entry to
    consistently quickly.

  9. This is very interesting, You are a very skilled
    blogger. I have joined your feed and look forward to seeking more of your great post.
    Also, I’ve shared your website in my social networks!

  10. Do you have a spam issue on this blog; I also am a blogger, and I was wanting to know your situation; many of us have developed some nice procedures and we are looking to trade strategies with other folks, be sure to shoot me an e-mail if interested.


电子邮件地址不会被公开。 必填项已用*标注