【BZOJ 4566】[HAOI2016] 找相同字符

相关链接

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

解题报告

我们可以拿一个串建SAM,把另一个串扔到SAM中匹配一遍
也可以直接把两个串拼一起,然后建SAM,最后遍历一下就好

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 800009;
const int SGZ = 27;
 
int n, m;
char s[N];
 
class Suffix_Automaton{
int cnt, tail, ch[N][SGZ], fail[N], sz[N][2], len[N], head[N], nxt[N], to[N];
public:
    inline void init() {
		cnt = tail = 1;
        for (int i = 1; i <= n; i++) {
            append(s[i] - 'a', 0);
        }
        append(SGZ - 1, -1);
        for (int i = n + 2; i <= n + m + 1; i++) {
            append(s[i] - 'a', 1);
        }
        for (int i = 1; i <= cnt; i++) {
            AddEdge(fail[i], i);
        }
        DFS(0, 0);
    }
    inline LL query() {
        LL ret = 0;
        for (int i = 1; i <= cnt; i++) {
            ret += (LL)(len[i] - len[fail[i]]) * sz[i][0] * sz[i][1];
        }
        return ret;
    } 
private:
    inline void DFS(int w, int f) {
        for (int i = head[w]; i; i = nxt[i]) {
            if (to[i] != f) {
                DFS(to[i], w);
                sz[w][0] += sz[to[i]][0];
                sz[w][1] += sz[to[i]][1];
            }
        }
    }
    inline void AddEdge(int u, int v) {
        static int E = 1;
        to[++E] = v; nxt[E] = head[u]; head[u] = E;
    }
    inline void append(char cc, int t) {
        int w = tail, cur = ++cnt;
        if (t != -1) {
            sz[cur][t] += 1;
        }
        len[cur] = len[tail] + 1;
        for (tail = cur; w && !ch[w][cc]; ch[w][cc] = cur, w = fail[w]);
        if (w) {
            if (len[ch[w][cc]] == len[w] + 1) {
                fail[cur] = ch[w][cc];
            } else {
                int nt = ++cnt, pt = ch[w][cc]; 
                memcpy(ch[nt], ch[pt], sizeof(ch[nt]));
                len[nt] = len[w] + 1;
                fail[nt] = fail[pt];
                fail[cur] = fail[pt] = nt;
                for (; w && ch[w][cc] == pt; ch[w][cc] = nt, w = fail[w]);
            }
        } else {
			fail[cur] = 1;
		}
    } 
}sam;
 
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    s[n + 1] = 'z' + 1;
    scanf("%s", s + n + 2);
    m = strlen(s + n + 2);
    sam.init();
    printf("%lld\n", sam.query());
    return 0;
}

【日常小测】Different Trips

题目大意

给定一棵$n(n \le 10^5)$个结点的树,每一个结点的特征值定义为这个结点的度
询问从根节点走到叶子结点的所有路径中本质不同的字符串的数量

解题报告

这题就是诸神眷顾的幻想乡的弱化版,撸一发广义SAM就可以了

不过GEOTCBRL考完之后给我们增加了一点姿势水平:

广义后缀自动机如果使用DFS建立的话,时间复杂度是$O($叶子结点深度和$)$的
如果使用BFS来建立的话,时间复杂度是$O(n \cdot$字符集大小$)$

这在15年刘研绎的集训队论文《后缀自动机在字典树上的拓展》中有详细的证明
其中还给出了构造极端数据的构造方法
所以这题字符集大小这么大的话,这样会T的
可能只有后缀数组才能做 QwQ

Code

这辣鸡代码是可以卡的,泥萌不要卡啊…….

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 2000009;
 
int n,head[N],nxt[N],to[N],in[N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    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;
}
 
inline void AddEdge(int u, int v) {
    static int E = 1; in[u]++; in[v]++;
    to[++E] = v; nxt[E] = head[u]; head[u] = E;
    to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
 
class Suffix_Automaton{
    int tot,len[N],fail[N],vis;
    map<int,int> ch[N];
    public:
        inline Suffix_Automaton() {tot=1;}
        inline int insert(int t, int c) {
            if (ch[t]&&len[ch[t]]==len[t]+1) return ch[t];
            int w = ++tot; len[w] = len[t] + 1;
            for (;t&&!ch[t];t=fail[t]) ch[t] = w;
            if (!t) fail[w] = 1;
            else if (len[ch[t]] == len[t] + 1) fail[w] = ch[t];
            else {
                int nt = ++tot, pt = ch[t];
                ch[nt] = ch[pt]; len[nt] = len[t] + 1;
                fail[nt] = fail[pt]; fail[pt] = fail[w] = nt;
                for (;t&&ch[t]==pt;t=fail[t]) ch[t] = nt;
            } return w;
        }
        inline LL GetAns() {
            LL ret = 0;
            for (int i=2;i<=tot;i++)
                ret += len[i] - len[fail[i]];
            return ret;
        }
}SAM;
 
void DFS(int w, int f, int ins) {
    int nins = SAM.insert(ins, in[w]);
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            DFS(to[i], w, nins);
        }
    }
}
 
int main() {
    n = read();
    for (int i=1;i<n;i++) AddEdge(read(), read());
    DFS(1, 1, 1);
    printf("%lld\n",SAM.GetAns());
    return 0;
}

【日常小测】String

题目大意

先给定一个长度为$n(n \le 50000)$的字符串$S$
之后给定$m(m \le 50000)$个操作(强制在线),操作分两种

  1. 在字符串$S$末尾加入一个字符
  2. 将$S$的子串$[l,r]$取出来,设为字符串$T$,询问$T$中出现至少两次的字符串的最长长度

解题报告

我们考虑用一棵线段树来支持插入斜率为$-1$的线段,并询问区间最值
这个是用来维护答案的,至于为什么插入的是线段,待会儿再说
至于具体实现,因为斜率相同,所以我们只需要将直线的纵截距插入即可,换言之我们只需要支持区间取$\max$即可

现在假设我们已经在维护了$[1,r-1]$的答案,并且我们在维护$[1,r]$回答所有右端点为$r$的询问
考虑插入第$r$个字符会影响哪些部分的答案:显然只会影响$fail$链上的答案
我们记录$last_x$表示$SAM$上的结点x代表的串在$S$中出现的最后一次的时间
我们注意到一条$fail$链上$last_x$一定是相等的,所以我们只需要考虑最长长度$l$
于是我们需要在线段树的$[last_x-l+1,last_x]$区间插入$x+y-(last_x+1)=0$的直线
之后我们更新$fail$链上的$last_x$,至于询问我们只需要到线段树上查询区间最值
当然维护$fail$树的话,我们需要使用$LCT$。

注意到$LCT$的一个$splay$里的$last_x$相等,所以单次$access$只会贡献$\log n$次区间取$\max$操作
所以我们已经能在$O(n \log ^2 n)$的时间复杂度内解决离线版本了
现在考虑在线版本,我们将线段树可持久化即可

【BZOJ 4199】[NOI2015] 品酒大会

相关链接

题目传送门Ⅰ:http://uoj.ac/problem/131
题目传送门Ⅱ:http://www.lydsy.com/JudgeOnline/problem.php?id=4199
神犇题解:https://blog.sengxian.com/solutions/bzoj-4199

解题报告

其实sengxian都写了题解了,我还有什么写的意义 _(:з」∠)_
不过还是简单说两句吧!

我们考虑把SA建出来,height数组搞出来
然后把height数组排个序
从小到大依次合并上去就可以辣!

Code

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

const int N = 600009; 
const LL INF = 1e18;

int n,val[N],sz[N],mx[N],mn[N]; 
int height[N],bot[N],sa[N],arr[N];
int *rak,*que,arr1[N],arr2[N],fa[N];
char pat[N]; LL ans1,ans2;
stack<pair<LL,LL> > ans;

inline int read() {
	char c=getchar(); int ret=0,f=1;
	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;
}

inline bool cmp(const int &a, const int &b) {
	return height[a] > height[b];
}

class Suffix_Array{
	public:
		inline void build() {
			rak = arr1; que = arr2;
			for (int i=1;i<=n;i++) bot[pat[i]-'a'+1]++;
			for (int i=1;i<=26;i++) bot[i] += bot[i-1];
			for (int i=1;i<=n;i++) sa[bot[pat[i]-'a'+1]--] = i;
			for (int ty=0,i=1;i<=n;i++) rak[sa[i]] = pat[sa[i]]==pat[sa[i-1]]? ty: ++ty;
			for (int l=1,tot=0,ty;l<n;l<<=1,tot=0) {
				memset(bot,0,sizeof(bot));
				for (int i=n-l+1;i<=n;i++) que[++tot] = i;
				for (int i=1;i<=n;i++) if (sa[i]>l) que[++tot] = sa[i] - l;
				for (int i=1;i<=n;i++) bot[rak[i]]++;
				for (int i=1;i<=n;i++) bot[i] += bot[i-1];
				for (int i=n;i;i--) sa[bot[rak[que[i]]]--] = que[i];
				swap(rak, que); rak[sa[1]] = ty = 1; bot[1] = 1;
				for (int i=2;i<=n;i++) 
					if (que[sa[i]] == que[sa[i-1]] && que[sa[i]+l] == que[sa[i-1]+l]) rak[sa[i]] = ty;
					else bot[rak[sa[i]] = ++ty] = 0;
				if (ty >= n) break;
			}
			Get_Height();
		}
		inline void solve() { 
			for (int i=1;i<=n;i++) {
				arr[i] = fa[i] = i; sz[i] = 1; 
				mn[i] = mx[i] = val[sa[i]];
			}
			sort(arr+1, arr+1+n, cmp);
			for (int i=n-1,j=1;~i;i--) {
				for (;height[arr[j]]>=i;++j) update(arr[j]);
				ans.push(make_pair(ans1, ans2));
			} 
			for (;!ans.empty();ans.pop()) 
				printf("%lld %lld\n",ans.top().first, ans.top().second);
		}	
	private:
		inline void Get_Height() {
			for (int i=1,len,p1,p2;i<=n;i++) {
				len = max(height[rak[i-1]] - 1, 0);
				p1 = i + len; p2 = sa[rak[i]-1] + len;
				while (pat[p1] == pat[p2]) ++p1, ++p2, ++len;
				height[rak[i]] = len;
			} height[1] = -1;
		}
		int find(int x) {return fa[x]==x?x:find(fa[x]);}
		inline void update(int i) { 
			static int E = 1; if (E) E = 0, ans2 = -INF;
			int f1 = find(i), f2 = find(i-1);
			ans1 += (LL)sz[f1] * sz[f2];
			ans2 = max(ans2, (LL)mx[f2] * mx[f1]);
			ans2 = max(ans2, (LL)mn[f2] * mn[f1]);
			sz[f1] += sz[f2]; fa[f2] = f1;
			mx[f1] = max(mx[f1], mx[f2]);
			mn[f1] = min(mn[f1], mn[f2]);
		}
}SA;

int main() {
	n = read();
	scanf("%s",pat+1);
	for (int i=1;i<=n;i++) val[i] = read();
	SA.build();
	SA.solve();
	return 0;
}

—————————— UPD 2017.7.10 ——————————
显然这货用SAM也是可做的

【日常小测】最长公共前缀

题目大意

给定一棵以$1$号点为根、大小为$n$的有根树($n \le 10^5$),每一条边上有一个小写英文字母
给定$m$个询问,第$i$个询问包含一个长度为$t_i$的点集(元素可重,$\sum{t_i} \le 2 \cdot 10^5$),询问$\sum\limits_{a=1}^{t_i}{\sum\limits_{b=a+1}^{t_i}{lcp(a,b)}}$

定义$s_a$为从a出发走向根,将边上的字符按顺序写下来构成的字符串
定义$lcp(a,b)$为$s_a$与$s_b$的最长公共前缀

下面举一个栗子
若树长成这样:

那么$s_5=cb,s_4=cbb$
更进一步,若某次询问的点集为$\{4,5\}$那么答案为$2$

解题报告

看到这种树上的字符串,我能想到AC自动机,或者广义后缀自动机
想了想AC自动机做不了,那就广义后缀自动机来做咯!

考虑后缀自动机上的Fail树
一个点的祖先实际上是这个点代表的字符串的后缀
那么题目中的$lcp(a,b)$就变成了$lca(a,b)$
于是对于每一次询问,我们建一个虚树出来
然后在虚树上DFS一次,统计一下答案就好啦!

另外,这题用后缀数组也可以做!
听武爷讲一讲,大概就是先把Trie树建出来
同时记录下每一次倍增的$Rank$数组(波兰表……)
然后就正常倍增,写法已经和罗穗骞的后缀数组的实现很不同了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
const int M = N << 1;
 
int n,m,E,head[N],nxt[M],to[M],col[M],pos[N],id[N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    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;
}
 
inline void Add_Edge(int u, int v, int c = 0) {
    to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c;
    to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c;
}   
 
class Suffix_Automaton{
	int cnt=1,ch[N][26],fail[N],vis[N],dep[N],sum[N];
	int tot,arr[N],que[N],len[N],fa[N][20],_hash[N];
	vector<int> G[N]; LL ans_tmp;
    public:
        inline int insert(int t, int cc) {
            if (ch[t][cc] && len[ch[t][cc]] == len[t] + 1) return ch[t][cc];
            int tail = ++cnt; len[tail] = len[t] + 1;
            while (!ch[t][cc] && t) ch[t][cc] = tail, t=fail[t];
            if (!t) fail[tail] = 1;
            else {
                if (len[ch[t][cc]] == len[t] + 1) fail[tail] = ch[t][cc];
                else {
                    int nw = ++cnt, w = ch[t][cc]; len[nw] = len[t]+1;
                    memcpy(ch[nw], ch[w], sizeof(ch[nw]));
                    fail[nw] = fail[w]; fail[w] = fail[tail] = nw;
                    for (;ch[t][cc]==w;t=fail[t]) ch[t][cc] = nw;
                }
            } return tail;
        }
        inline void Build_Fail_Tree() {
            memset(head,0,sizeof(head)); E = 0;
            for (int i=2;i<=cnt;i++) Add_Edge(fail[i], i);
            dfs(1, 1);
            for (int j=1;j<20;j++) {
                for (int i=1;i<=cnt;i++) {
                    fa[i][j] = fa[fa[i][j-1]][j-1];
                }
            }   
        }
        inline LL solve(int nn) {
            for (int i=1;i<=nn;i++) arr[i] = pos[read()];
            sort(arr+1, arr+1+nn, [](const int &a, const int &b) {return id[a] < id[b];});
            for (int i=1;i<=nn;i++) _hash[i] = arr[i];
            int mm = nn; nn = unique(arr+1, arr+1+nn) - arr - 1;
            for (int i=1;i<=nn;i++) sum[i] = 0;
            for (int i=1,j=1;i<=mm;i++) {
                while (arr[j] != _hash[i]) j++;
                sum[j]++;
            }
            que[tot=1] = 1; int MX = 1;
            for (int i=1,lca;i<=nn;i++) {
                vis[arr[i]] = sum[i];
                lca = LCA(que[tot], arr[i]);
                while (dep[que[tot]] > dep[lca]) {
                    if (dep[que[tot-1]] >= dep[lca]) G[que[tot-1]].push_back(que[tot]);
                    else G[lca].push_back(que[tot]);
                    --tot;
                }
                if (que[tot] != lca) que[++tot] = lca;
                if (arr[i] != que[tot]) que[++tot] = arr[i];
                MX = max(MX, tot);
            }
            while (tot > 1) G[que[tot-1]].push_back(que[tot]), --tot;
            ans_tmp = 0;
            Get_Ans(1);
            return ans_tmp;
        }
    private:
        void dfs(int w, int f) {
            static int id_count = 0;
            id[w] = ++id_count;
            fa[w][0] = f; dep[w] = dep[f] + 1;
            for (int i=head[w];i;i=nxt[i]) {
                if (to[i] != f) {
                    dfs(to[i], w);
                }
            }
        } 
        int Get_Ans(int w) {
            int ret = vis[w]; 
            if (w > 1) ans_tmp += vis[w] * (vis[w] - 1ll) / 2 * len[w]; 
            for (int i=G[w].size()-1,tmp;~i;i--) { 
                tmp = Get_Ans(G[w][i]);
                ans_tmp += (LL)tmp * ret * len[w];
                ret += tmp;
            }
            vis[w] = 0; 
            G[w].clear();
            return ret;
        }
        inline int LCA(int a, int b) {
            if (dep[a] < dep[b]) swap(a, b);
            for (int i=19;~i;i--) if (dep[fa[a][i]] >= dep[b]) a = fa[a][i];
            if (a == b) return a;
            for (int i=19;~i;i--) if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
            return fa[a][0];
        }   
}SAM;
 
void DFS(int w, int f, int t) {
    pos[w] = t;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            int nt = SAM.insert(t, col[i]);
            DFS(to[i], w, nt);
        }
    }
}
 
int main() {
    n = read(); char pat[10];
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        scanf("%s",pat+1);
        Add_Edge(u, v, pat[1] - 'a');
    }   
    DFS(1, 1, 1);
    SAM.Build_Fail_Tree();
    for (int i=read();i;i--) 
        printf("%lld\n",SAM.solve(read()));
    return 0;
}

【BZOJ 3926】[ZJOI2015] 诸神眷顾的幻想乡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3926
神犇题解:http://wjmzbmr.com/archives/zjoi-2015-day-1题解/

解题报告

陈老师的语文真刺激!
把叶节点最多只有20个这个条件埋得那么深 QwQ
一开始以为那个条件意思是度数不超过20,于是想边分治,后来都想到”万径人踪灭”去了……

考虑树上每一条路径,至少存在一个叶子结点,使得将该叶子结点作为根后,这条路径上的结点深度递减
于是对于每一个叶节点都DFS一遍,然后建广义后缀自动机
广义自动机的话,直接看这份代码就好吧!
或者想全面学习的话,可以看这里:传送门

另外,这题据陈老师说,后缀数组也可以做
但我不会啊,跪求神犇带 _(:з」∠)_

Code

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

const int N = 200000+9;
const int M = 2000000;
const int C = 10;

int n,c,col[N],head[N],to[N],nxt[N],in[N];

class Suffix_Automaton{
	int ch[M][C],pre[M],len[M],cnt;
	public:
		inline int insert(int last, int t) {
			int w = ++cnt; len[w] = len[last] + 1; pre[0] = -1;
			for (;~last&&!ch[last][t];last=pre[last]) ch[last][t] = w;
			if (~last) {
				if (len[ch[last][t]] == len[last] + 1) {
					pre[w] = ch[last][t];
				} else {
					int nw = ++cnt, tmp = ch[last][t];
					len[nw] = len[last] + 1; 
					pre[nw] = pre[tmp]; pre[tmp] = pre[w] = nw; 
					memcpy(ch[nw],ch[tmp],sizeof(ch[nw]));
					for (;~last&&ch[last][t]==tmp;last=pre[last]) ch[last][t] = nw;
				}
			} return w;
		} 
		inline LL solve() {
			LL ret = 0;
			for (int i=1;i<=cnt;i++)
				ret += len[i] - len[pre[i]];
			return ret; 
		}
}SAM;

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

inline void Add_Edge(int u, int v) {
	static int E = 1; in[u]++; in[v]++;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS(int w, int f, int s) {
	int rt = SAM.insert(s, col[w]);
	for (int i=head[w];i;i=nxt[i]) 
		if (to[i] != f) DFS(to[i], w, rt);
}

int main() {
	n = read(); c = read();
	for (int i=1;i<=n;i++) col[i] = read();
	for (int i=1;i<n;i++) Add_Edge(read(),read());
	for (int i=1;i<=n;i++) if (in[i] == 1) DFS(i, i, 0);
	printf("%lld\n",SAM.solve());
	return 0;
}

【BZOJ 4516】[SDOI2016] 生成魔咒

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

考试的时候,一看到要动态维护就把SA扔一边凉快去了QAQ
想一想,不能这么草率啊!
来说一说SA和SAM两种做法

1) SAM:
很明显就是求一个字符串本质不同的字串个数
SAM本身就是增量构造,于是就成裸题了

2) SA:
考虑离线之后,先逆序建一个完整的出来
那么加入一个字符,实际上就是加入了一个后缀
那么其对于答案的贡献,就是原来的height数组搞一搞
实现的话,搞一个RMQ什么的就好
代码的话,我们来召唤Menci:https://oi.men.ci/sdoi2016-incantation/

自己太懒,于是就只写了SAM的代码:

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

const int N = 200000+9; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	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;
}

namespace Suffix_Automaton{
	#define SAM Suffix_Automaton
	int len[N],fail[N],cnt,tail;
	unordered_map<int,int> ch[N]; 
	
	inline int Extend(int c) {
		int w = tail; tail = ++cnt; len[tail] = len[w] + 1;
		while (w&&!ch[w]) ch[w] = cnt, w = fail[w];
		if (!w) fail[tail] = 1;
		else {
			if (len[ch[w]] == len[w]+1) fail[tail] = ch[w];
			else {
				int to = ch[w]; ch[++cnt] = ch[to];
				fail[cnt] = fail[to]; fail[to] = cnt; fail[tail] = cnt; 
				len[cnt] = len[w] + 1; while (ch[w] == to) ch[w] = cnt, w = fail[w];
			}
		} return len[tail] - len[fail[tail]];
	}
	
	inline void solve(int n) {
		cnt = tail = 1; 
		for (LL i=1,vout=0;i<=n;i++) 
			printf("%lld\n",vout+=Extend(read()));
	}
};

int main(){
	SAM::solve(read());
	return 0;
}

—– UPD 2016.9.29 —–
这™map比unordered_map快这么多有几个意思QAQ
475864785645
这种感觉……
真·生无可恋
V5[YANBJ`4%A2`%PIH$BH_F

【NOI五连测】[D3T2] 加密

题目传送门:http://pan.baidu.com/s/1qYPBdpU
数据生成器:http://paste.ubuntu.com/19351549/
OJ传送门:http://oi.cdshishi.net:8080/Problem/1719

这道题目,一看,SA的板题嘛!于是很高兴的码了SA
码完之后一对拍,发现,好像常数很大的样子,然而一看数据范围,嗯,一定是O(nlogn)的复杂度
结果,又被卡常了QAQ

说一说SA的做法:
首先在SA上二分,搞出len
然后再次在SA上二分,搞出最小的标号
然后总体复杂度O(6*n*log(n)),于是T了一个点QAQ

再来说一说SAM的做法(QJC说:这不是SAM的一眼题吗QAQ)
两个字串的lcp,是fail树上的lca,于是考虑在lca上染色的话,O(n)即可
另外,此题不是要求的不是后缀关系,是前缀关系,于是我们倒着建即可

SA版本:

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

const int MAXN = 1000000+9;
const int SGZ = 26;
const int INF = 100000000;

char pat[MAXN];
int n;

namespace Suffix_Array{
	#define SA Suffix_Array
	int height[MAXN],sa[MAXN],t1[MAXN],t2[MAXN],bot[MAXN];
	int *tmp,*rank,m,K[MAXN],LEN[MAXN];
	
	inline void ST_Advance(){
		for (int i=1,k,len;i<=n;i++) {
			k = 0, len = 1;
			while (len < i) len *= 2, k++;
			K[i] = k; LEN[i] = len;
		}
	}
	
	struct Sparse_Table{
		int MN[MAXN][20];
		
		inline void init(int *arr){
			for (int i=1;i<=n;i++) MN[i][0] = arr[i];
			for (int k=1,lim=2;k<=19;k++,lim=1<<k) for (int i=1;i<=n-lim+1;i++)
				MN[i][k] = min(MN[i][k-1], MN[i+(1<<(k-1))][k-1]);
		}
		
		inline int query(int a, int b){
			if (a > b) swap(a, b); 
			int sta=(b-a+2)/2,k=K[sta],len=LEN[sta];
			return min(MN[a][k], MN[b-len+1][k]);
		}
	}ST_num,ST_hei;
	
	inline void GetHeight(){
		for (int i=1;i<=n;i++) if (rank[i] > 1) {
			int sta = max(0, height[rank[i-1]]-1);
			int p1 = sta + i, p2 = sta + sa[rank[i]-1];
			while (pat[p1++] == pat[p2++]) sta++;
			height[rank[i]] = sta;
		}
	}
	
	inline void build(){
		tmp = t1, rank = t2;
		n = strlen(pat+1); m = SGZ;
		for (int i=1;i<=n;i++) bot[tmp[i]=pat[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 (tmp[sa[i]] != tmp[sa[i-1]]) rank[sa[i]] = ++m;
			else rank[sa[i]] = m;
		
		for (int k=1;k<=n;k*=2) { int 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();
		ST_Advance();
		ST_num.init(sa);
		ST_hei.init(height);
	}
	
	inline void solve(){
		for (int w=1,tag=0;w<n;tag=0) {
			int mid, l = 1, r = rank[w] - 1, len = 0, ans = 0;
			while (l <= r) {
				mid = (l + r) / 2;
				if (ST_num.query(rank[w]-mid,rank[w]-1) < w) r = mid-1, len = mid;
				else l = mid+1;
			}
			if (len) ans = ST_hei.query(rank[w]-len+1, rank[w]);
			
			l = 1; r = n - rank[w]; len = 0;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (ST_num.query(rank[w]+1, rank[w]+mid) < w) r = mid-1, len = mid;
				else l = mid+1; 
			} 
			if (len) ans = max(ans, ST_hei.query(rank[w]+1, rank[w]+len));
			
			if (ans) {
				printf("%d ",ans); tag = ans;
				l = 1; r = rank[w]; len = 0; ans = INF;
				while (l <= r) {
					mid = (l + r) / 2;
					if (ST_hei.query(rank[w], rank[w]-mid+1) >= tag) l = mid+1, len = mid;
					else r = mid-1; 
				} 
				if (len) ans = ST_num.query(rank[w]-len,rank[w]-1);
				l = 1; r = n-rank[w]; len = 0;
				while (l <= r) {
					mid = (l + r) / 2;
					if (ST_hei.query(rank[w]+1, rank[w] + mid) >= tag) l = mid+1, len = mid;
					else r = mid-1;			
				}
				if (len) ans = min(ans, ST_num.query(rank[w]+1, rank[w]+len));
				printf("%d ",ans-1); w += tag;
			} else {
				printf("%d %d ",-1,(int)pat[w]);
				w ++;
			}
		}
	}
};

int main(){
	freopen("encrypt.in","r",stdin);
	freopen("encrypt.out","w",stdout);
	scanf("%s",pat+1);
	SA::build();
	SA::solve();
	return 0;
}

SAM版本:

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

const int MAXN = 1000000+9;
const int SGZ = 27;

char pat[MAXN];
int n;

namespace Suffix_Automaton{
	#define SAM Suffix_Automaton
	int ch[MAXN][SGZ],fail[MAXN],tag[MAXN],W=1;
	int cnt,last,dep[MAXN],pos[MAXN];
	
	inline void extend(int i, int c){
		int w = last; dep[pos[i]=last=++cnt] = dep[w]+1; 
		while (w && !ch[w]) ch[w] = last, w = fail[w];
		if (!ch[w]) fail[last] = 1;
		else {
			int nw = ch[w];
			if (dep[nw] == dep[w] + 1) fail[last] = nw;
			else {
				int nnw = ++cnt; dep[nnw] = dep[w] + 1;
				memcpy(ch[nnw],ch[nw],sizeof(ch[nw]));
				fail[nnw] = fail[nw]; fail[nw] = fail[last] = nnw;
				while (ch[w] == nw) ch[w] = nnw, w = fail[w];
			}
		}
	}
	
	inline void sign(int w, int val) {
		while (w && !tag[w]) 
			tag[w] = val, w = fail[w];
		if (W == val) {
			if (w <= 1) printf("-1 %d ",(int)pat[val]), W++;
			else printf("%d %d ",dep[w],tag[w]-1), W += dep[w]; 
		}
	}
	
	inline void build(char *s){
		n = strlen(s+1); cnt = last = 1;
		for (int i=n;i;i--) extend(i, pat[i]-'a'+1);
		for (int i=1;i<=n;i++) sign(pos[i], i);
	}
};

int main(){
	scanf("%s",pat+1);
	SAM::build(pat);
	return 0;
} 

看看SA将近4k的代码
再看看SAM只有1.2k的代码
SA,你还要我怎么爱你QAQ

【BZOJ 3998】[TJOI2015] 弦论

相关链接

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

解题报告

这个,SAM求k小串的板题,然而我这个纸张写了两次、调了7h+才过QAQ     (浅谈模板写挂了的悲伤有多大.pdf
t==0 -> 后缀自动机的每一个节点只代表一个串
t==1 -> 后缀自动机的每一个节点代表|fail数的大小|个节点
然后顺着走一走就好。

Code

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

const int MAXN = 1000000+9;
const int SGZ = 26;

char pat[MAXN];
int n,t; LL k;

namespace Suffix_Automaton{
	#define SAM Suffix_Automaton
	int ch[MAXN][SGZ],fail[MAXN],sz[MAXN],len[MAXN];
	int cnt,last,bot[MAXN],ord[MAXN]; LL cho[MAXN];
		
	inline void extend(int c){
		int w = last; last = ++cnt; 
		len[last] = len[w]+1; sz[last]=1;
		while (w && !ch[w]) ch[w] = last, w=fail[w];
		if (!w) fail[last] = 1;
		else {
			int nw = ch[w];
			if (len[nw] == len[w]+1) fail[last] = nw;
			else {
				int nnw = ++cnt; len[nnw] = len[w]+1;
				for (int i=0;i<SGZ;i++) ch[nnw][i]=ch[nw][i];
				fail[nnw] = fail[nw]; fail[nw] = fail[last] = nnw;
				while (w && ch[w]==nw) ch[w] = nnw, w = fail[w];
			}
		}
	}
	
	inline void build(){
		cnt = last = 1;
		n = strlen(pat+1);
		for (int i=1;i<=n;i++)
			extend(pat[i]-'a');
	}
	
	inline void sign(){
		for (int i=1;i<=cnt;i++) bot[len[i]]++;
		for (int i=1;i<=n;i++) bot[i] += bot[i-1];
		for (int i=cnt;i;i--) ord[bot[len[i]]--] = i;
		
		if (t == 1) for (int j=cnt,i=ord[j];j;i=ord[--j]) sz[fail[i]] += sz[i];
		else for (int i=2;i<=cnt;i++) sz[i] = 1;
		
		for (int j=cnt,i=ord[j];j;i=ord[--j]){
			cho[i] += (LL)sz[i];
			for (int c=0;c<SGZ;c++) 
				cho[i] += cho[ch[i]];
		}
	}
	
	inline void solve(){
		if (cho[1] < k) printf("-1\n");
		else {
			int w = 1; while (k > 0){
				for (int c=0;c<SGZ && k>0;c++) 
					if (cho[ch[w]] < k) k -= cho[ch[w]];
					else {putchar(c+'a');w=ch[w];k-=sz[w];break;}
			}
		}	
	}
};

int main(){
	scanf("%s%d%lld",pat+1,&t,&k);
	SAM::build();
	SAM::sign();
	SAM::solve();
	return 0;
}

【BZOJ 3238】[AHOI2013] 差异

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

这个东西,想了想,不会做QAQ于是可耻地看题解,果断SA算贡献
最近在做专题,又看到这个题,发现SAM算贡献不是更好算吗QAQ
贴一个SA的代码吧!SAM就偷懒不写啦!o( ̄▽ ̄)ブ

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

const int MAXN = 1000000+9;

namespace Suffix_Array{
	int sa[MAXN],bot[MAXN],t1[MAXN],t2[MAXN],height[MAXN],*rank,*tmp;
	int n,m;
	
	inline void build(char *s){
		n = strlen(s+1); m = 26;
		rank = t1; tmp = 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++) rank[sa[i]] = s[sa[i]]==s[sa[i-1]]?m:++m;
		
		for (int k=1;k<=n;k*=2){
			int tot = 0; 
			for (int i=1;i<=m;i++) bot[i] = 0;
			for (int i=n-k+1;i<=n;i++) tmp[++tot] = i;
			for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++tot] = sa[i] - k;
			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(rank, tmp); 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 void GetHeight(char *s){
		for (int i=1;i<=n;i++) if (rank[i] > 1) {
			int sta = max(0, height[rank[i-1]]-2);
			int p1 = i+sta, p2 = sa[rank[i]-1]+sta;
			while (s[p1++] == s[p2++]) sta++;
			height[rank[i]] = sta;
		}
	}
};

int L[MAXN],R[MAXN]; LL vout;
int cnt,que[MAXN],pos[MAXN]; 

inline void GetAns(){
	using namespace Suffix_Array;
	for(int i=1;i<=n;i++) vout += (LL)i*(LL)(n-1);
	
	cnt = 0;
	for (int i=1;i<=n;i++){ while (cnt && que[cnt] >= height[i]) cnt--;
		L[i] = pos[cnt]+1;
		que[++cnt] = height[i]; pos[cnt] = i;
	} 
	
	cnt = 0; pos[0] = n+1;
	for (int i=n;i;i--){
		while (cnt && que[cnt] > height[i]) cnt--;
		R[i] = pos[cnt]-1;
		que[++cnt] = height[i]; pos[cnt] = i;
	} 
	
	for (int i=1;i<=n;i++) vout -= 2LL*(LL)(i-L[i]+1)*(LL)(R[i]-i+1)*(LL)height[i];
	printf("%lld",vout);
}

char pat[MAXN];
int main(){
	scanf("%s",pat+1);
	SA::build(pat);
	SA::GetHeight(pat); 
	GetAns(); 
	return 0;
}

【HDU 5442】Favorite Donut

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5442
数据生成器:http://paste.ubuntu.com/18084370/

这题,SA可做,SAM可做,最小表示法可做
然而我的SA对拍怎么都过不了,本地不错,交上去就wa,弃疗

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

const int MAXN = 1600000+9;
const int SIGMA_SIZE = 30;

char pat[MAXN];
int n;

namespace Suffix_Array{
	#define SA Suffix_Array
	int sa[MAXN],height[MAXN],bot[MAXN];
	int t1[MAXN],t2[MAXN],*tmp,*rank;
	int m,cnt,Pos[MAXN],ord[MAXN],wor[MAXN];
	
	inline void GetHeight(){
		for (int i=1;i<=n;i++) height[i] = 0;
		for (int i=1;i<=n;i++) if (rank[i] > 1){
			int sta = max(0,height[rank[i-1]]-2);
			int p1 = i+sta, p2 = sa[rank[i]-1]+sta;
			while (pat[p1++] == pat[p2++]) sta++;
			height[rank[i]] = sta;
		}
	}
	
	inline void build(){
		memset(bot,0,sizeof(bot));
		memset(height,0,sizeof(height));
		
		tmp = t1; rank = t2;
		n = strlen(pat+1); m = SIGMA_SIZE;
		for (int i=1;i<=n;i++) bot[tmp[i]=pat[i]-'a'+2]++;
		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 (tmp[sa[i]]==tmp[sa[i-1]]) rank[sa[i]] = m;
			else rank[sa[i]] = ++m;
			
		for (int k=1;k<=n;k*=2){int 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(rank, tmp);
			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();
	}
	
	inline bool sort_cmp(const int a, const int b){
		if (Pos[a] != Pos[b]) return Pos[a] < Pos[b];
		else return wor[a] < wor[b]; } inline bool judge(int i, int pos){ if ((pos>=1&&pos<=n/4) || (pos>=n/2+2&&pos<=n/2+n/4+1)){ cnt=1; if (pos>=1&&pos<=n/4) Pos[cnt]=pos, wor[cnt]=0; else Pos[cnt]=n/2+n/4+2-pos, wor[cnt]=1; while (height[i--] >= n/4){
				pos = sa[i];
				if (pos>=1&&pos<=n/4) Pos[++cnt]=pos, wor[cnt]=0; else if (pos>=n/2+2&&pos<=n/2+n/4-1) Pos[++cnt]=n/2+n/4+2-pos, wor[cnt]=1;
			}
			
			for (int j=1;j<=cnt;j++) ord[j] = j; sort(ord+1,ord+1+cnt,sort_cmp); printf("%d %d\n",Pos[ord[1]],wor[ord[1]]); return true; } else return false; } inline void solve(){ for (int i=n;i;i--) if (judge(i,sa[i])) break; } }; int main(){ int T; cin>>T;
	while (T--){
		scanf("%d%s",&n,pat+1); 
		for (int i=1;i<=n;i++) pat[n+i] = pat[i]; n *= 2;
		for (int i=1;i<=n;i++) pat[n+i+1] = pat[n-i+1];
		pat[n+1] = 'a'-1; n=n*2+1; pat[n+1] = 0;
		SA::build();
		SA::solve();
	}	
	return 0;
}

【BZOJ 3670】[Noi2014] 动物园

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3670
离线版题目:http://paste.ubuntu.com/17902051/

想了很久。最后觉得SAM+链剖+主席树可捉,一看数据范围,这个有问题啊!
于是可耻的看了题解,我再也不敢说KMP简单了,MD小性质有一堆QAQ
干货写在《KMP总结》里,这里只扔一份代码吧!

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

const int MAXN = 1000000+9;
const LL MOD = 1000000007;

char pat[MAXN];
int n,fail[MAXN],cnt[MAXN];

int main(){
	int T; cin>>T;
	while (T--){
		scanf("%s",pat+1);
		n = strlen(pat+1); cnt[1] = 1;
		for (int i=2,j=0;i<=n;i++){
			while (j && pat[j+1] != pat[i]) j = fail[j];
			if (pat[j+1] == pat[i]) j++;
			fail[i] = j; cnt[i] = cnt[fail[i]] + 1;
		} LL vout = 1;
		for (int i=2,j=0;i<=n;i++){ while (j && pat[j+1] != pat[i]) j = fail[j]; if (pat[j+1] == pat[i]) j++; while (j && j*2 > i) j = fail[j];
			vout = (vout*(cnt[j]+1)) % MOD;
		}
		printf("%d\n",int(vout));
	}
	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;
} 

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