差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:lgwza:回文树 [2020/10/03 20:00]
lgwza 创建
+++ 2020-2021:teams:legal_string:lgwza:回文树 [2020/10/03 23:54] (当前版本)
lgwza
@@ 行 79: / 行 79: @@
 </code>
 </hidden>
+===== 例题 =====
+[[https://www.luogu.com.cn/problem/P5496|P5496 【模板】回文自动机 (PAM)]]
+**题意**：给定一个字符串 $s$。保证每个字符为小写字母。对于 $s$ 的每个位置，请求出以该位置结尾的回文子串个数。
+**题解**：理解好模板中的 $last$ 和 $num[]$ 的意义即可做。
+**评价**：实现了 **功能 4**。
+**代码**：
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=5e5+5;
+struct Palindromic_Tree{
+    int nxt[N][26],fail[N],cnt[N],num[N],len[N],S[N],last,n,p;
+    int newnode(int l){
+        memset(nxt[p],0,sizeof(nxt[p]));
+        cnt[p]=num[p]=0;
+        len[p]=l;
+        return p++;
+    }
+    void init(){
+        p=0;
+        newnode(0);
+        newnode(-1);
+        last=0;
+        n=0;
+        S[n]=-1;
+        fail[0]=1;
+    }
+    int get_fail(int x){
+        while(S[n-len[x]-1]!=S[n]) x=fail[x];
+        return x;
+    }
+    void add(int c){
+        c-='a';
+        S[++n]=c;
+        int cur=get_fail(last);
+        if(!nxt[cur][c]){
+            int now=newnode(len[cur]+2);
+            fail[now]=nxt[get_fail(fail[cur])][c];
+            nxt[cur][c]=now;
+            num[now]=num[fail[now]]+1;
+        }
+        last=nxt[cur][c];
+        cnt[last]++;
+    }
+    void count(){
+        for(int i=p-1;i>=0;i--) cnt[fail[i]]+=cnt[i];
+    }
+}P;
+char s[N];
+int main(){
+    scanf("%s",s);
+    int len=strlen(s);
+    P.init();
+    P.add(s[0]);
+    int k=P.num[P.last];
+    printf("%d",k);
+    for(int i=1;i<len;i++){
+        P.add((s[i]-97+k)%26+97);
+        k=P.num[P.last];
+        printf(" %d",k);
+    }
+    return 0;
+}
+</code>
+</hidden>
+[[https://www.luogu.com.cn/problem/P3649|P3649 [APIO2014]回文串]]
+**题意**：给你一个由小写拉丁字母组成的字符串 $s$。我们定义 $s$ 的一个子串的存在值为这个子串在 $s$ 中出现的次数乘以这个子串的长度。对于给你的这个字符串 $s$，求所有回文子串中的最大存在值。
+**题解**：利用模板中的 $len[]$ 和 $cnt[]$ 即可。
+**评价**：利用了 **功能 2**。
+**代码**：
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=3e5+5;
+struct Palindromic_Tree{
+    int nxt[N][26],fail[N],cnt[N],num[N],len[N],S[N],last,n,p;
+    int newnode(int l){
+        memset(nxt[p],0,sizeof(nxt[p]));
+        cnt[p]=num[p]=0;
+        len[p]=l;
+        return p++;
+    }
+    void init(){
+        p=0;
+        newnode(0);
+        newnode(-1);
+        last=0;
+        n=0;
+        S[n]=-1;
+        fail[0]=1;
+    }
+    int get_fail(int x){
+        while(S[n-len[x]-1]!=S[n]) x=fail[x];
+        return x;
+    }
+    void add(int c){
+        c-='a';
+        S[++n]=c;
+        int cur=get_fail(last);
+        if(!nxt[cur][c]){
+            int now=newnode(len[cur]+2);
+            fail[now]=nxt[get_fail(fail[cur])][c];
+            nxt[cur][c]=now;
+            num[now]=num[fail[now]]+1;
+        }
+        last=nxt[cur][c];
+        cnt[last]++;
+    }
+    void count(){
+        for(int i=p-1;i>=0;i--) cnt[fail[i]]+=cnt[i];
+    }
+}P;
+char s[N];
+int main(){
+    P.init();
+    scanf("%s",s);
+    int len=strlen(s);
+    for(int i=0;i<len;i++) P.add(s[i]);
+    P.count();
+    long long maxx=0;
+    for(int i=0;i<P.p;i++){
+        maxx=max(maxx,1ll*P.len[i]*P.cnt[i]);
+    }
+    printf("%lld",maxx);
+    return 0;
+}
+</code>
+</hidden>
+[[https://www.luogu.com.cn/problem/P1659|P1659 [国家集训队]拉拉队排练]]
+**题意**：连续的一段奇回文串被称作和谐小群体，找出所有和谐小群体并按长度降序排列后，求前 $K$ 个的长度之积并取模。
+**题解**：利用模板的 $cnt[]$ 和 $len[]$ 数组来处理。
+**代码**：
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=1e6+5,mod=19930726;
+typedef long long ll;
+ll fastpow(int x,int y){
+    ll ret=1;
+    for(;y;y>>=1,x=1ll*x*x%mod)
+        if(y&1) ret=1ll*ret*x%mod;
+    return ret;
+}
+struct Palindromic_Tree{
+    int nxt[N][26],fail[N],cnt[N],len[N],S[N],last,n,p;
+    int newnode(int l){
+        memset(nxt[p],0,sizeof(nxt[p]));
+        cnt[p]=0;
+        len[p]=l;
+        return p++;
+    }
+    void init(){
+        p=0;
+        newnode(0);
+        newnode(-1);
+        last=0;
+        n=0;
+        S[n]=-1;
+        fail[0]=1;
+    }
+    int get_fail(int x){
+        while(S[n-len[x]-1]!=S[n]) x=fail[x];
+        return x;
+    }
+    void add(int c){
+        c-='a';
+        S[++n]=c;
+        int cur=get_fail(last);
+        if(!nxt[cur][c]){
+            int now=newnode(len[cur]+2);
+            fail[now]=nxt[get_fail(fail[cur])][c];
+            nxt[cur][c]=now;
+        }
+        last=nxt[cur][c];
+        cnt[last]++;
+    }
+    void count(){
+        for(int i=p-1;i>=0;i--) cnt[fail[i]]+=cnt[i];
+    }
+}P;
+char s[N];
+bool cmp(const pair<int,int>&a,const pair<int,int>&b){
+    return a.first>b.first;
+}
+int main(){
+    P.init();
+    ll n,k;
+    scanf("%lld %lld",&n,&k);
+    scanf("%s",s);
+    int len=strlen(s);
+    for(int i=0;i<len;i++) P.add(s[i]);
+    P.count();
+    ll K=0;
+    vector<pair<int,int>>v;
+    for(int i=0;i<P.p;i++)
+        if(P.len[i]>0&&(P.len[i]&1))
+            K+=P.cnt[i],v.push_back(make_pair(P.len[i],P.cnt[i]));
+    if(K<k){
+        printf("-1");return 0;
+    }
+    sort(v.begin(),v.end(),cmp);
+    ll ans=1;
+    for(int i=0;i<v.size();i++){
+        if(k<=0) break;
+        if(k>=v[i].second){
+            ans=(ans*1ll*fastpow(v[i].first,v[i].second))%mod;
+            k-=v[i].second;
+        }
+        else{
+            ans=(ans*1ll*fastpow(v[i].first,k))%mod;
+            break;
+        }
+    }
+    printf("%lld",ans);
+    return 0;
+}
+</code>
+</hidden>
+[[https://www.luogu.com.cn/problem/P4287|P4287 [SHOI2011]双倍回文]]
+**题意**：记字符串 $w$ 的倒置为 $w^R$。如果 $x$ 能够写成 $ww^Rww^R$ 的形式，则称它是一个“双倍回文”。给定字符串，计算它的最长双倍回文子串的长度。
+**题解**：利用好 $trans$ 指针的性质即可。
+**代码**：
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=5e5+5;
+struct Palindromic_Tree{
+    int nxt[N][26],fail[N],cnt[N],num[N],len[N],S[N],last,n,p;
+    int trans[N];
+    int newnode(int l){
+        memset(nxt[p],0,sizeof(nxt[p]));
+        cnt[p]=num[p]=0;
+        len[p]=l;
+        return p++;
+    }
+    void init(){
+        p=0;
+        newnode(0);
+        newnode(-1);
+        last=0;
+        n=0;
+        S[n]=-1;
+        fail[0]=1;
+    }
+    int get_fail(int x){
+        while(S[n-len[x]-1]!=S[n]) x=fail[x];
+        return x;
+    }
+    void add(int c){
+        c-='a';
+        S[++n]=c;
+        int cur=get_fail(last);
+        if(!nxt[cur][c]){
+            int now=newnode(len[cur]+2);
+            fail[now]=nxt[get_fail(fail[cur])][c];
+            nxt[cur][c]=now;
+            num[now]=num[fail[now]]+1;
+            if(len[now]<=2) trans[now]=fail[now];
+            else{
+                int tmp=trans[cur];
+                while(S[n-len[tmp]-1]!=S[n]||((len[tmp]+2)<<1)>len[now]) tmp=fail[tmp];
+                trans[now]=nxt[tmp][c];
+            }
+        }
+        last=nxt[cur][c];
+        cnt[last]++;
+    }
+    void count(){
+        for(int i=p-1;i>=0;i--) cnt[fail[i]]+=cnt[i];
+    }
+}P;
+char s[N];
+int len[N];
+int main(){
+    int n;
+    scanf("%d",&n);
+    scanf("%s",s);
+    P.init();
+    int ans=0;
+    for(int i=0;i<n;i++){
+        P.add(s[i]);
+    }
+    for(int i=1;i<P.p;i++){
+        if((P.len[P.trans[i]]<<1)==P.len[i]&&P.len[P.trans[i]]%2==0)
+            ans=max(ans,P.len[i]);
+    }
+    printf("%d",ans);
+    return 0;
+}
+</code>
+</hidden>
+[[https://ac.nowcoder.com/acm/contest/7817/A|2020牛客国庆集训派对day1 A]]
+**题意**：在给定字符串末尾添加尽可能少的字符使其成为回文串。
+**题解**：该等价于求解以原字符串末尾字符结尾的最长回文子串，直接用回文自动机秒杀。
+**代码**：
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=4e5+5;
+struct Palindromic_Tree{
+    int nxt[N][26],fail[N],len[N],S[N],last,n,p;
+    int newnode(int l){
+        memset(nxt[p],0,sizeof(nxt[p]));
+        len[p]=l;
+        return p++;
+    }
+    void init(){
+        p=0;
+        newnode(0);
+        newnode(-1);
+        last=0;
+        n=0;
+        S[n]=-1;
+        fail[0]=1;
+    }
+    int get_fail(int x){
+        while(S[n-len[x]-1]!=S[n]) x=fail[x];
+        return x;
+    }
+    void add(int c){
+        c-='a';
+        S[++n]=c;
+        int cur=get_fail(last);
+        if(!nxt[cur][c]){
+            int now=newnode(len[cur]+2);
+            fail[now]=nxt[get_fail(fail[cur])][c];
+            nxt[cur][c]=now;
+        }
+        last=nxt[cur][c];
+    }
+}P;
+char s[N];
+int main(){
+    P.init();
+    int n;
+    scanf("%d",&n);
+    scanf("%s",s);
+    for(int i=0;i<n;i++){
+        P.add(s[i]);
+    }
+    printf("%d",n-P.len[P.last]);
+    return 0;
+}
+</code>
+</hidden>
+===== 参考链接 =====
+[[https://oi-wiki.org/string/pam/|OI Wiki 回文树]]
+[[https://www.cnblogs.com/DWVictor/p/11324247.html|回文树总结]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具