【BZOJ 3103】[ONTAK2010] Palindromic Equivalence

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3103
神犇题解:http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence

解题报告

这些字符串相关的计数题已经做过很多了吧?
这题显然就是给定$O(n)$个相等与不等的关系,让你求染色方案数
这样直接做好像是一个$NP$的问题?就是四色定理那个一般化后的问题

但这题有一个非常好的性质,如果我们把一个等价类看成点,不等关系看成边
那么每一个联通块都是一个完全图!也就是一个弦图!
弦图的染色方案数是可以使用完美消除序列在$O(n)$的时间复杂度内解决的
有因为这题是完全图,所以任意一个$1 \sim n$的排列都是完美消除序列
于是直接从$1 \to n$进行计算即可

至于这图是个弦图图的证明,想一想还是很简单的(虽然不怎么容易观察出来)
我们可以参考:http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000009;
const int M = N << 1;
const int MOD = 1000000007;

char pat[N],s[N];
int n,ans=1,fa[N],rid[N],col[N];
int vis[N],head[N],nxt[M],to[M]; 
vector<pair<int,int> > e;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int find(int x) {
	return x == fa[x]? x: fa[x] = find(fa[x]);
}

inline void manacher() {
	for (int i=1,r=1,p=1,t;i<=n*2;i++) {
		t = min(r - i, rid[p - (i - p)]);
		while (s[i+t+1] == s[i-t-1]) t++, fa[find(i+t)] = find(fa[i-t]);
		if ((rid[i] = t) + i > r) r = t + i, p = i;
		e.push_back(make_pair(i - t - 1, i + t + 1));
	}
}

inline void AddEdge(int u, int v) {
	static int E = 1; 
	if (u == v || !(u & 1) || !(v & 1)) return;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

int main() {
	scanf("%s",pat+1); n = strlen(pat+1); 
	s[0] = '#'; s[n*2] = '@';
	for (int i=1;i<=n;i++) s[i*2-1] = pat[i], s[i*2] = '*';
	for (int i=1;i<=n*2;i++) fa[i] = i;
	manacher();
	for (int i=0;i<e.size();i++) AddEdge(find(e[i].first), find(e[i].second));
	for (int i=1,cnt;cnt=26,i<=n*2;i+=2) {
		if (find(i) != i) continue; col[i] = 1;
		for (int j=head[i];j;j=nxt[j]) {
			if (col[to[j]] && vis[to[j]] < i) 
				--cnt, vis[to[j]] = i;
		}  
		if (cnt <= 0) ans = 0; 
		else ans = (LL)ans * cnt % MOD;
	}
	cout<<ans;
	return 0;
}

—————————— UPD 2017.4.26 ——————————
今天我们机房讨论了一下,这货是个弦图,不一定是一个完全图

【BZOJ 1414】[ZJOI2009] 对称的正方形

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1414

题号“1414”,还真的是把我做得“要死要死的”!做了一整天QAQ
Hash version:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
 
const int MX = 0;
const int MAXN = 2000+9;
unsigned int SEEDX = 37;
unsigned int SEEDY = 137;
 
int n,m; LL vout;
unsigned int px[2000+9],py[2000+9],mat[MAXN][MAXN],f[5][MAXN][MAXN];
 
inline int read(){
    char c=getchar(); int ret=0;
    while (c<'0'||c>'9') c=getchar();
    while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
    return ret;
}
 
inline void init(){
    m = read(); n = read(); vout = (unsigned int)n*m;
    for (int j=1;j<=m;j++) {
        for (int i=1;i<=n*2+1;i++) mat[i][j*2-1] = MX;
        for (int i=1;i<=n;i++) mat[i*2][j*2] = read(), mat[i*2-1][j*2] = MX;
        mat[n*2+1][j*2] = MX;
    } for (int i=1;i<=n*2+1;i++) mat[i][m*2+1] = MX;
    n = n*2+1; m = m*2+1;
}
 
inline void Hash_init(){
    px[0] = 1; for (int i=1;i<=2001;i++) px[i] = SEEDX*px[i-1];
    py[0] = 1; for (int i=1;i<=2001;i++) py[i] = SEEDY*py[i-1];
    for (int i=n,g=1;i;i--,g++) for (int j=1,h=1;j<=m;j++,h++) f[1][i][j] = px[g]*py[h]*mat[i][j] + f[1][i+1][j] + f[1][i][j-1] - f[1][i+1][j-1];
    for (int i=1,g=1;i<=n;i++,g++) for (int j=1,h=1;j<=m;j++,h++) f[2][i][j] = px[g]*py[h]*mat[i][j] + f[2][i-1][j] + f[2][i][j-1] - f[2][i-1][j-1];
    for (int i=1,g=1;i<=n;i++,g++) for (int j=m,h=1;j;j--,h++) f[3][i][j] = px[g]*py[h]*mat[i][j] + f[3][i-1][j] + f[3][i][j+1] - f[3][i-1][j+1];
    for (int i=n,g=1;i;i--,g++) for (int j=m,h=1;j;j--,h++) f[4][i][j] = px[g]*py[h]*mat[i][j] + f[4][i+1][j] + f[4][i][j+1] - f[4][i+1][j+1];
}
 
inline unsigned int Get_Hash(int t, int x1, int y1, int x2, int y2){
    if (t == 1) return (f[1][x1][y1] + f[1][x2+1][y2-1] - f[1][x2+1][y1] - f[1][x1][y2-1]) * px[2001-(n-x1+1)] * py[2001-y1];
    else if (t == 2) return (f[2][x1][y1] + f[2][x2-1][y2-1] - f[2][x2-1][y1] - f[2][x1][y2-1])* px[2001-x1] * py[2001-y1];
    else if (t == 3) return (f[3][x1][y1] + f[3][x2-1][y2+1] - f[3][x2-1][y1] - f[3][x1][y2+1]) * px[2001-x1] * py[2001-(m-y1+1)];
    else return (f[4][x1][y1] + f[4][x2+1][y2+1] - f[4][x2+1][y1] - f[4][x1][y2+1]) * px[2001-(n-x1+1)] * py[2001-(m-y1+1)];
}
 
inline bool judge(int x, int y, int len){
    unsigned int t1 = Get_Hash(1,x,y,x+len,y-len),t2 = Get_Hash(2,x,y,x-len,y-len);
    if (t1 != t2) return false;
    t1 = Get_Hash(3,x,y,x-len,y+len);
    if (t1 != t2) return false;
    t2 = Get_Hash(4,x,y,x+len,y+len);
    if (t1 != t2) return false;
    else return true;
}
 
inline void solve(){
    for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if ((i&1) + (j&1) != 1) {
        int l=2,r=min(min(i-1,j-1),min(n-i,m-j)),ans=0,mid;
        while (l <= r) {
            mid = l + r >> 1;
            if (judge(i,j,mid)) l = mid+1, ans = mid;
            else r = mid-1;
        }vout += ans/2;
    }
}
 
int main(){
    init(); Hash_init(); solve();
    printf("%lld\n",vout);
    return 0;
}  

Manacher version:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
 
const int MAXN = 2000+9;
 
int mat[MAXN][MAXN],n,m,tmp[MAXN],ans[MAXN],que[MAXN],tot,pos[MAXN];
int res_x[MAXN][MAXN],res_y[MAXN][MAXN],sa_y[MAXN][MAXN],sa_x[MAXN][MAXN];
 
inline int read(){
    char c=getchar(); int ret=0;
    while (c<'0'||c>'9') c=getchar();
    while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
    return ret;
}
 
inline void manacher(int lim){
    int MX=0; ans[0] = 0;
    for (int i=1;i<=lim;i++) {
        if (MX+ans[MX] > i) ans[i] = min(MX+ans[MX]-i, ans[MX*2-i]);
        else ans[i] = 0;
        while (tmp[i+ans[i]+1] == tmp[i-ans[i]-1]) ans[i]++;
        if (ans[i]+i > MX+ans[MX]) MX = i;
    }
}
 
inline void DP(int lim){
    tot = 0; pos[0] = 0; int sta = 0;
    for (int i=1;i<=lim;i++) {
        while (tot && ans[i] <= que[tot]) tot--; sta = min(sta, tot);
        que[++tot] = ans[i]; pos[tot] = i; int w = sta;
        while (w < tot && min(que[w],(i-pos[w-1])*2-1) <= min(que[w+1],(i-pos[w])*2-1)) w++;
        sta = w; tmp[i] = min(que[w],(i-pos[w-1])*2-1);
    } 
}

int main(){
    m = read(); n = read();
    for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) mat[i*2][j*2] = read();
    n = n * 2 + 1; m = m * 2 + 1;
     
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) tmp[j] = mat[i][j]; tmp[0] = -1; tmp[m+1] = -2;
        manacher(m); 
        for (int j=1;j<=m;j++) sa_y[i][j] = ans[j];
    }
    for (int j=1;j<=m;j++) {
        for (int i=1;i<=n;i++) ans[i] = sa_y[i][j]*2+1;
        DP(n);
        for (int i=1;i<=n;i++) res_x[i][j] = tmp[i];
        for (int i=1;i*2<=n;i++) swap(ans[i],ans[n-i+1]);
        DP(n);
        for (int i=1;i<=n;i++) res_x[i][j] = min(res_x[i][j],tmp[n-i+1]);
    } 
         
    for (int j=1;j<=m;j++) {
        for (int i=1;i<=n;i++) tmp[i] = mat[i][j]; tmp[0] = -1; tmp[n+1] = -2;
        manacher(n); 
        for (int i=1;i<=n;i++) sa_x[i][j] = ans[i];
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) ans[j] = sa_x[i][j]*2+1;
        DP(m);
        for (int j=1;j<=m;j++) res_y[i][j] = tmp[j];
        for (int j=1;j*2<=m;j++) swap(ans[j],ans[m-j+1]);
        DP(m);
        for (int j=1;j<=m;j++) res_y[i][j] = min(res_y[i][j], tmp[m-j+1]);
    } 
     
    LL vout = (n/2)*(m/2);
    for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) if ((i+j) % 2 == 0)
        vout += max(0,(min(res_x[i][j]-1,res_y[i][j]-1)/2)/2);
    printf("%lld\n",vout);
    return 0;
} 

【BZOJ 2342】[Shoi2011] 双倍回文

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2342

manacher自己做的第一题! 2A! 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
最开始看这个题:树套树?二维偏序的既视感……然而树套树求取区间最值的空间复杂度绝对过不了
于是可耻看题解,瞄了一眼:用set就可以水掉QAQ
于是再自己推一推,确定两个set连起来就可以搞
搞一搞520ms水过去了
再一看题解,还可以只用一个set水过去QAQ
不过跑出来反而比hzwer的一个set快一点……..

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;

const int MAXN = 1200000; 

char pat[MAXN],BUF[MAXN];
int p[MAXN],rt,n,len,vout;

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

inline void init(){
	scanf("%d%s",&n,BUF+1);
	for (int i=1;i<=n;i++){
		pat[i*2-1] = '@';
		pat[i*2] = BUF[i];
	} pat[n*2+1] = '@';
	pat[0] = '#'; pat[n*2+2] = '$';
}

struct cmp{
	bool operator () (const int &a, const int &b){
		return a+p[a] < b+p[b];
	}
}; 

set<int> por;
set<int,cmp> list;
set<int>::iterator itr;
set<int,cmp>::iterator ITR;
pair<set<int,cmp>::iterator,bool> TMP;

inline void solve(){
	for (int i=3;i<=len;i+=2){
		int p1 = i-p[i]/2,buf=0;
		itr = por.lower_bound(p1);
		if (itr != por.end()){  
			buf = (i-*itr+1)/2;
			vout = max(vout, buf*4);
		}
			
		TMP = list.insert(i);
		if (TMP.second) por.insert(i);		
		
		ITR = list.begin();
		while (!list.empty() && *ITR+p[*ITR] < i+2) 
			por.erase(*ITR), list.erase(ITR),ITR = list.begin();
	}
	printf("%d",vout);
}

int main(){
	init();
	manacher();
	solve(); 
	return 0;	
} 

【BZOJ 3325】[Scoi2013] 密码

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3325
离线版题目:http://paste.ubuntu.com/18029355/
数据生成器:http://paste.ubuntu.com/18029394/

最近都在做字符串,所以接触了一点逆向字符串的题目,于是这题就会做啦!
这类给你字符串结构的过程数组,叫你统计方案数/构造符合要求的字符串,说到底就是给了你一堆字符等与不等的关系
而你就需要根据具体数据结构的特点来处理这些关系
比如说这道题,我上周六想了半个小时,一点思路都没有,觉得提供的关系可能是O(n^2)的。
但今天再来想的时候发现,相等关系可以用和manacher时间复杂度一样的整法证到时O(n)的
而不等关系很明显是O(n)的,于是保存好关系,并查集缩一缩点就搞好啦!
基本上1A! 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*

#include<iostream>
#include<cstdio>
#include<set>
#define SITR set<int>::iterator
using namespace std;

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

const int MAXN = 100000+9;
const int SIGMA_SIZE = 26;

int ld[MAXN],lo[MAXN],fa[MAXN];
int n,mx=1,vout[MAXN],col[MAXN];
set<int> Q[MAXN];

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f=fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline void connect(int a, int b){
	int f1=find(a), f2=find(b);
	if (f1 != f2) fa[f1] = f2;
}

inline void discon(int a, int b){
	Q[fa[a]].insert(fa[b]);
	Q[fa[b]].insert(fa[a]);
}

int main(){
	n = read(); 
	for (int i=1;i<=n;i++) fa[i] = i; 
	for (int i=1;i<=n;i++) ld[i] = (read()-1)/2;
	for (int i=1;i<n;i++)  lo[i] = read()/2;
	
	for (int i=1;i<=n;i++){
		for (int j=max(mx-i+1,1);j<=ld[i];j++)
			connect(i+j,i-j);	
		mx = max(mx, i+ld[i]);
		
		for (int j=max(mx-i+1,1);j<=lo[i];j++)
			connect(i+j,i-j+1);		
		mx = max(mx, i+lo[i]);
	}
	for (int i=1;i<=n;i++)  fa[i]=find(i);
	for (int i=1;i<=n;i++){ if (i-ld[i] > 1 && i+ld[i] < n) discon(i+ld[i]+1,i-ld[i]-1); if (i-lo[i] > 0 && i+lo[i] < n) 
			discon(i+lo[i]+1,i-lo[i]);
	}
	
	for (int i=1;i<=n;i++){
		if (vout[fa[i]]) continue;
		else {
			for (SITR j=Q[fa[i]].begin();j!=Q[fa[i]].end();j++)
				col[vout[*j]] = i;
			for (int j=1;j<=SIGMA_SIZE;j++)
				if (col[j] < i) {vout[fa[i]] = j; break;}
		}
	}
	
	for (int i=1;i<=n;i++) putchar(vout[fa[i]]+'a'-1);
	
	return 0;
}

【Codeforces 100548G】The Problem to Slow Down You

题目传送门:http://codeforces.com/gym/100548 ps:是G题

首先,这个题目肯定可以用manacher配合SA/SAM来完成,然而SA/SAM的代码不好写QAQ
但是我们发现,需要的所有串都是回文串,所以可以建两个PAM,然后一起跑DFS
1A 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 200000+9;
const int SIGMA_SIZE = 26;

struct Palindromic_Tree{
	#define PAM Palindromic_Tree
	int ch[MAXN][SIGMA_SIZE],fail[MAXN];
	int cnt,last,n,sz[MAXN],len[MAXN];
	char *pat; LL ret;
	
	inline int newnode(){
		cnt += 1;
		memset(ch[cnt],0,sizeof(ch[cnt]));
		fail[cnt] = sz[cnt] = len[cnt] = 0;
		return cnt;
	}
	
	inline void init(){
		cnt = last = 1; 
		fail[0] = fail[1] = 1;
		sz[0] = sz[1] = len[0] = 0; len[1] = -1;
		memset(ch[0],0,sizeof(ch[0]));
		memset(ch[1],0,sizeof(ch[1]));
	}
	
	inline void extend(int p, int c){
		int w = last;
		while (pat[p-len[w]-1] != pat[p]) w = fail[w];
		if (!ch[w]){
			int nw = newnode(),k=fail[w]; len[nw] = len[w]+2;
			while (pat[p-len[k]-1] != pat[p]) k = fail[k];
			fail[nw] = ch[k]; ch[w] = nw;
		}
		last = ch[w];
		sz[last]++;
	}
	
	inline void build(char *s){
		init(); pat = s;
		n = strlen(s+1);
		for (int i=1;i<=n;i++)
			extend(i,s[i]-'a');
		for (int i=cnt;i;i--)
			sz[fail[i]] += sz[i];
	}
	
	void DFS(int pa, int pb, PAM *s){
		if (pa > 1 && pb > 1) ret += (LL)sz[pa]*(LL)s->sz[pb];
		for (int i=0;i<SIGMA_SIZE;i++)
			if (ch[pa][i] && s->ch[pb][i])
				DFS(ch[pa][i],s->ch[pb][i],s);
	}
	
	inline LL solve(PAM *a){
		ret = 0LL;
		DFS(0,0,a);
		DFS(1,1,a);
		return ret;
	}
}A,B;

char sa[MAXN],sb[MAXN];

int main(){
	int T,TT=0; cin>>T;
	while (T--){
		scanf("%s%s",sa+1,sb+1);
		A.build(sa); B.build(sb);	
		printf("Case #%d: %I64d\n",++TT,A.solve(&B));
	}
	return 0;
} 

【Tsinsen 1280】最长双回文串

题目传送门:http://www.tsinsen.com/ViewGProblem.page?gpid=A1280
离线版题目:http://paste.ubuntu.com/17832836/

参考BZOJ_3676

#include<iostream>
#include<cstdio>
#include<cstring>
#include
<map>
using namespace std;

const int MAXN = 200000+9;
char pat[MAXN],BUF[MAXN/2];
int n,len[MAXN],vout;

map<int,int>::iterator itr;
map<int,int> Q;

inline void manacher(){
    int mx = 0;
    for (int i=1;i<=n;i++){ if (mx+len[mx] > i) len[i] = min(len[mx*2-i],mx+len[mx]-i);
        else len[i] = 0;
        while (pat[i+len[i]+1] == pat[i-len[i]-1]) len[i]++;
        if (len[i]+i > len[mx]+mx) mx = i;
    }
}

inline void init(){
    scanf("%s",BUF+1);
    n = strlen(BUF+1); vout = 2;
    for (int i=1;i<=n;i++){
        pat[i*2-1] = '*';
        pat[i*2] = BUF[i];
    } pat[n*2+1] = '*';
    n=n*2+1; pat[0]='@'; pat[n+1]='&';
}

inline void solve(){
    for (int i=1;i<=n;i++){ itr = Q.lower_bound(i-len[i]); if (itr != Q.end()){ int p = itr->second;
            vout = max(vout,i-p);
        }
         
        if ((Q.insert(make_pair(i+len[i], i))).second){
            itr = Q.find(i+len[i]);
            if (i >= (++itr)->second && itr != Q.end()) Q.erase(--itr);  
            else{
                itr--;
                while (itr != Q.begin() && (--itr)->second >= i) Q.erase(itr), itr=Q.find(i+len[i]);
            }
        }
    }
}

int main(){
    init();
    manacher();
    solve();
    printf("%d\n",vout);
    return 0;
}

【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;
}

【BZOJ 3790】神奇项链

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3790
离线版题目:http://paste.ubuntu.com/17470379/
吐槽:板题,直接上代码不解释

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 120000;

char pat[MAXN],chr[MAXN];
int n,l[MAXN],r[MAXN],len[MAXN],ord[MAXN];

namespace FenwickTree{
	#define BIT FenwickTree
	#define low(x) (x&(-x))
	#define INF 1000000000
	int arr[MAXN],buf[MAXN];

	inline void init(){
		for (int i=1;i<=n;i++)
			arr[i] = buf[i] = INF;
	}

	inline int query(int left, int right){
		if (right < left) return INF; else { int ret = INF; while (right >= left){
				if (right-low(right)+1>=left) ret = min(ret,arr[right]),right-=low(right);
				else ret = min(ret,buf[right]), right--;
			}
			return ret;
		}
	}

	inline void modify(int pos, int nv){
		if (buf[pos] > nv) {
			buf[pos] = nv;
			for (int i=pos;i<=n;i+=low(i)) if (arr[i] > nv) arr[i] = nv;
				else break;
		} else return;
	}
};

inline bool sort_cmp(const int &A, const int &B){
	return r[A] < r[B];
}

inline int manacher(){
	int m=n*2+1,itr=0;
	for (int i=1;i<=n;i++)
		chr[i*2-1] = '@',
		chr[i*2] = pat[i];
	chr[m] = '@'; chr[m+1] = '#'; chr[0] = '$';

	for (int i=1,p1,p2;i<=m;i++){ if (itr+len[itr] > i)  len[i] = min(len[2*itr-i],itr+len[itr]-i);
		else len[i] = 0;
		p1 = i-len[i]; p2 = i+len[i];
		while (chr[--p1] == chr[++p2]) len[i]++;
		if (itr+len[itr] < i+len[i]) itr = i;
	}

	for (int i=1;i<=m;i++)
		r[i] = i+len[i],
		l[i] = i-len[i],
		ord[i] = i;
	sort(ord+1,ord+m,sort_cmp);

	n = m; BIT::init(); BIT::modify(1,0);
	for (int j=1,i=ord[j],tmp;j<=n;j++,i=ord[j]){
		tmp = BIT::query(l[i],r[i]-1)+1;
		BIT::modify(r[i],tmp);
	}

	return BIT::query(m-1,m)-1;
}

int main(){
	while (~scanf("%s",pat+1)){
		n = strlen(pat+1);
		printf("%dn",manacher());
	}
	return 0;
}