題目鏈接：點擊查看

題目大意：給出一個字符串 s ，求最長雙回文子串，題目規定最長雙回文子串 t 可以拆成左右兩部分，滿足兩部分都是回文串

題目分析：一開始讀錯題了，以為是雙回文串本身也需要是回文串，結果發現并不是，這樣的話直接用回文自動機求就好了，其中有個參數len數組正好代表了以某個點為結尾的最長回文后綴的長度，正著跑一遍維護一個最長回文后綴的長度，然后再倒著跑一遍維護答案就好了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;char s[N];int suf[N];struct Palindrome_tree {int nxt[N][26];int fail[N]; // 當前節點最長回文后綴的節點int len[N]; // 當前節點表示的回文串的長度int cnt[N]; // 當前節點回文串的個數， 在getcnt后可得到全部int sed[N]; // 以當前節點為后綴的回文串的個數（并不是表示第i結尾的回文串的種類數，如果要求每個點結尾的數的回文串個數，得用last）int record[N]; //record記錄了節點回文串的結束位置char s[N];int tot; // 節點個數int last; // 上一個節點int n;//當前字符串的長度 void init(){tot = n = 0;memset(fail, 0, sizeof fail);memset(cnt, 0, sizeof cnt);memset(sed, 0, sizeof sed);memset(len, 0, sizeof len);memset(nxt, 0, sizeof nxt);}void build(){len[0] = 0, len[1] = -1; // 0為偶數長度根， 1為奇數長度根tot = 1, last = 0;fail[0] = 1;}int getfail(int x, int n){while (s[n - len[x] - 1] != s[n]||n-len[x]-1<0) // 比較x節點回文串新建兩端是否相等//n-len[x]-1<0這個是我自己加的，多組的時候光第一個條件是不夠的，所以有錯請手動刪除x = fail[x]; // 若不同， 再比較x后綴回文串兩端return x;}void insert(char ch){int c = ch - 'a';//全小寫要用a 全大寫要用A 不然會錯s[++n]=ch;int p = getfail(last, n);// 得到第i個字符可以加到哪個節點的兩端形成回文串if (!nxt[p][c]){tot++;len[tot] = len[p] + 2; // 在p節點兩端添加兩個字符fail[tot] = nxt[getfail(fail[p], n)][c]; //tot點的后綴回文，可以由上一個節點的后綴回文嘗試得到sed[tot] = sed[fail[tot]] + 1; // 以當前節點為結尾的回文串個數nxt[p][c] = tot; // 新建節點}last = nxt[p][c]; // 當前節點成為上一個節點cnt[last]++; //當前節點回文串++record[last] = n;}void get_cnt(){for (int i = tot; i > 0; i--)cnt[fail[i]] += cnt[i];//fail[i] 的節點 為 i 節點的后綴回文串， 所以個數相加} }tree;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%s",s);int n=strlen(s);tree.init();tree.build();for(int i=0;i<n;i++){tree.insert(s[i]);suf[i]=tree.len[tree.last];}tree.init();tree.build();int ans=0;for(int i=n-1;i>=1;i--){tree.insert(s[i]);ans=max(ans,suf[i-1]+tree.len[tree.last]);}printf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的HYSBZ - 2565 最长双回文串(回文自动机)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。