[APIO2014]回文串
2021-03-23 00:23
阅读：697
输出样例#2：
View Code
4
这道题好像是一道回文树裸题
但是我并不会回文树
可以用SA＋manacher或SAM+manacher
最近刚学 SAM ，所以用 SAM+manacher 过掉了这道题
首先先对原串建立 SAM
然后跑 manacher ，一旦有回文串就在SAM上进行查询
查询 S(l , r)在原串中出现多少次
暴力查询一次的复杂度是 O(n)
总复杂度 O(n^2)
显然不能通过此题
所以我们可以考虑用倍增快速查询出 S(l,r) 在原串中出现次数
设 st[i][j] 表示 SAM 上的节点i向上跳 2^j 步能到达哪个节点
如果当前节点的 step >= r - l + 1 就说明要查询的回文串仍然是当前节点的一个后缀
就一直往上跳到不能再跳为止
此时的节点所代表的子串的 right 集合大小就是 S(l,r) 在原串中的出现次数辣
这样的时间复杂度 O(nlogn)，可以通过此题
#include#include #include #include # define LL long long const int M = 600005 ; using namespace std ; char s[M] ; int n , m ; LL Ans ; int Last , cnt ; int size[M] , son[M][26] , fa[M] , step[M] , c[M] , b[M] ; int p[M] , r[M] , fir[M] ; int pos[M] , lg[M] , dep[M] , st[M][20] ; inline void Insert(int c , int id){ int np = ++cnt , p = Last ; step[np] = step[p] + 1 ; Last = cnt ; size[np] = 1 ; pos[id] = np ; while(!son[p][c] && p) son[p][c] = np , p = fa[p] ; if(!p) fa[np] = 1 ; else { int q = son[p][c] ; if(step[q] == step[p] + 1) fa[np] = q ; else{ int nq = ++cnt ; step[nq] = step[p] + 1 ; memcpy(son[nq] , son[q] , sizeof(son[q])) ; fa[nq] = fa[q] ; fa[q] = fa[np] = nq ; while(son[p][c] == q) son[p][c] = nq , p = fa[p] ; } } } inline void Build(){ Last = cnt = 1 ; for(int i = 1 ; i ‘a‘ , i) ; for(int i = 1 ; i ; for(int i = 1 ; i 1] ; for(int i = 1 ; i i ; for(int i = cnt , p ; i ; i --) { p = b[i] ; size[fa[p]] += size[p] ; } for(int i = 1 , p ; i ) { p = b[i] ; dep[p] = dep[fa[p]] + 1 ; st[p][0] = fa[p] ; for(int j = 1 ; (1) st[p][j] = st[st[p][j - 1]][j - 1] ; } } inline void Check(int l , int r){ if(l 1 || r > n) return ; int now = pos[r] ; for(int i = lg[dep[now]] ; i >= 0 ; i --) { int temp = st[now][i] ; if(step[temp] >= r - l + 1) now = temp ; } Ans = max(Ans , 1LL * size[now] * (r - l + 1)) ; } inline void Manacher() { p[++m] = ‘@‘ ; for(int i = 1 ; i ‘#‘ , p[++m] = s[i] , fir[m] = i ; p[++m] = ‘#‘ ; p[++m] = ‘$‘ ; int pos = 0 , mx = 0 ; for(int i = 1 ; i ) { if(i 2 - i]) ; else r[i] = 1 ; Check(fir[i - r[i] + 2] , fir[i + r[i] - 2]) ; while(p[i - r[i]] == p[i + r[i]]) ++r[i] , Check(fir[i - r[i] + 2] , fir[i + r[i] - 2]) ; if(i + r[i] > mx) mx = i + r[i] , pos = i ; } } int main(){ scanf("%s",s + 1) ; n = strlen(s + 1) ; for(int i = 2 ; i > 1] + 1 ; Build() ; Manacher() ; printf("%lld\n",Ans) ; return 0 ; }
上一篇：jQuery元素绑定事件
下一篇：C# 委托 Delegate
评论
亲，登录后才可以留言！