【BZOJ 3676】[Apio2014] 回文串

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3676
离线版题目:http://paste.ubuntu.com/17527319/
数据生成:http://paste.ubuntu.com/17528560/

哎呀,现在是下午5:47,我为了写这道题,现在周末作业只完成了1/3,呵呵呵呵!
来说一说坎坷的历程吧:
1. 10min 确定 SA + manacher
2. 1h 码完代码
3. 6h 调试代码,BZOJ仍然超时QAQ
4. UOJ上发现原题,提交,通过!
讲到这里,我只能说,BZOJ数据好强!
————————————————— 我是华丽丽的分割线,下面才是正文 ———————————————————
解题思路:manacher找出所有本质不同的回文串,sa来查询出现了多少次
被卡原因:SA模板出错,ST表模板出错,manacher的使用还有一点小问题
HINT:
1.网上很多代码都有问题,比如hzwer的就可以被“abbababbbb”卡掉,正解7,hzwer输出8(他的马拉车写错了)
2.BZOJ数据太强,SA + manacher要T,不过UOJ可过(其实在manacher那里分类讨论的话,也是可以卡过的
3.会用SAM的就不要用SA做死啦(或者你要用DC3应该也是可以过的,但是我不会QAQ
4.会用回文自动机的就不要用manacher做死啦!
5.刚才都说了网上的代码可能有错,所以能过就好
6.此题必须不放过任意一个本质不同的回文串,否则正确性有问题,哎呀刚才自己出的那组数据找不到了QAQ
7.答案会爆int
Inspiration:对于manacher来说,本质不同的回文串一定是能使右边界指针向右移的串
AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#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(){
	gets(BUF+1);
	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;
		ST::init();
	}

	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];

			swap(tmp,rank);
			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;
		}

		GetHeight(s);
	}


	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;
	}
	printf("%lldn",vout);
}

int main(){
	init();
	SA::build(pat);
	manacher();
	return 0;
}

来补一发后缀自动机,这简直是屠场啊!
AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#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];
		sz[last]++;
	}

	inline void build(char *s){
		init();
		n = strlen(s+1);
		for (int i=1;i<=n;i++)
			expend(i,s[i]-'a',s);
	}

	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(){
	scanf("%s",pat+1);
	PAM::build(pat);
	printf("%lldn",PAM::solve());
	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
    next!

  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.

发表评论

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