差别

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

--- 2020-2021:teams:legal_string:lgwza:回文树 [2020/10/03 20:02]
lgwza
+++ 2020-2021:teams:legal_string:lgwza:回文树 [2020/10/03 23:54] (当前版本)
lgwza
@@ 行 315: / 行 315: @@
     }
     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;
 }

CVBB ACM Team

用户工具

站点工具

差别

页面工具