題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)字符串，詢問該字符串中的所有回文子串中，各有多少不同的字母

題目分析：這個(gè)題題意很簡單，在比賽的時(shí)候看到字符串第一反應(yīng)是哈希，哈希+暴力+線段樹果不其然的T掉了。。還超了一秒鐘，完完全全的是算法的問題，所以就沒再碰那個(gè)題了，賽后對(duì)這個(gè)題一直很在意，磨了一個(gè)星期，可算是磨出來了，期間的過程也是艱難險(xiǎn)阻嗷，這個(gè)題目的正解是用回文自動(dòng)機(jī)來做（好像一切有關(guān)于回文串的問題都能用這個(gè)來做，太強(qiáng)了），于是就想去偷學(xué)一波，因?yàn)樾枰爸弥R(shí)是關(guān)于fail指針的理解，就先花了兩天肝會(huì)了KMP，然后又去看回文自動(dòng)機(jī)了，看了兩天還是不太懂fail邊是怎么建的，只會(huì)用模板，但不太會(huì)用，隨后去網(wǎng)上看有沒有別的方法，還有一個(gè)馬拉車的，還有一個(gè)就是哈希+二分判斷回文串的，學(xué)了一手，就可以用logn的時(shí)間來判斷每個(gè)點(diǎn)為中點(diǎn)的最長回文串了，再配合上動(dòng)態(tài)規(guī)劃記錄一下每個(gè)字母上一次出現(xiàn)的位置，就可以以O(shè)(26)的時(shí)間復(fù)雜度查詢一段區(qū)間內(nèi)每個(gè)字母出現(xiàn)過的次數(shù)了，這一塊我也不太懂，是交給隊(duì)友研究的，最后一組合起來，二分+哈希+動(dòng)態(tài)規(guī)劃，總時(shí)間復(fù)雜度是n*logn*26，完美解決了這個(gè)問題

等以后學(xué)會(huì)了回文自動(dòng)機(jī)在來回顧一下這個(gè)題吧。。現(xiàn)在還是太菜了

---

2020.2.6更新：

刷字符串剛好想起來還有這樣一道題，回來看了一眼題意，回文自動(dòng)機(jī)模板粘貼，稍微修改一下內(nèi)部實(shí)現(xiàn)，10分鐘不到一氣呵成完成AC，回首看看半年前的自己是真的弱，當(dāng)時(shí)徐州這場比賽我們隊(duì)出了三個(gè)題目，在學(xué)校里的rank是倒數(shù)第一。。不多說了，今年加油吧

回文自動(dòng)機(jī)來解這個(gè)題的話，只需要在每個(gè)節(jié)點(diǎn)再維護(hù)一下顏色的個(gè)數(shù)就好了，我選擇的是用狀態(tài)壓縮，因?yàn)橐还膊?6個(gè)字母，一個(gè)int整數(shù)就可以保存，題目問的是每個(gè)回文子串的貢獻(xiàn)，所以我們還需要維護(hù)一下每個(gè)節(jié)點(diǎn)所出現(xiàn)的次數(shù)，最后O(n)遍歷一遍每個(gè)節(jié)點(diǎn)維護(hù)答案就好了

上代碼：

哈希+二分+動(dòng)態(tài)規(guī)劃：

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=3e5+100;ull hash1[N],hash2[N],p[N];string str;int n;void HASH() {hash1[0]=0;hash2[n+1]=0;for(int i=1;i<=n;i++)hash1[i]=hash1[i-1]*131+str[i]-'a'+1;for(int i=n;i>=1;i--)hash2[i]=hash2[i+1]*131+str[i]-'a'+1;p[0]=1;for(int i=1;i<=n;i++)p[i]=p[i-1]*131; } int pos[N][30];bool check(int i,int len,bool sta)sta=1:奇數(shù)回文串 sta=0:偶數(shù)回文串 {int l,r;if(sta){l=i-len;r=i+len;}else{l=i-len;r=i+len+1;}if(l<=0||r>n)return false;ull a=hash1[r]-hash1[l-1]*p[r-l+1];ull b=hash2[l]-hash2[r+1]*p[r-l+1];return a==b; }LL getval(int l,int r)//獲得區(qū)間內(nèi)有多少不同的字母 {LL ans=0;for(int i=0;i<26;i++){LL temp=pos[r][i]-l+1;if(temp<0)continue;ans+=temp;}return ans; }int main() { // freopen("input.txt","r",stdin);while(cin>>str){n=str.size();str=" "+str;HASH(); for(int i=0;i<26;i++)pos[0][i]=-1;for(int i=1;i<=n;i++)//dp存每個(gè)字母前一次出現(xiàn)的位置 {for(int j=0;j<26;j++)pos[i][j]=pos[i-1][j];pos[i][str[i]-'a']=i;}LL ans=0;for(int i=1;i<=n;i++)//統(tǒng)計(jì)所有奇數(shù)回文串{int l=0;int r=n;int len;while(l<=r){int mid=l+r>>1;if(check(i,mid,1)){len=mid;l=mid+1;}else{r=mid-1;}}int x=i-len;int y=i;ans+=getval(x,y);}for(int i=1;i<n;i++)//統(tǒng)計(jì)所有偶數(shù)回文串{int l=0;int r=n;int len=-1;while(l<=r){int mid=l+r>>1;if(check(i,mid,0)){len=mid;l=mid+1;}else{r=mid-1;}}if(len==-1)continue;int x=i-len;int y=i;ans+=getval(x,y);}printf("%lld\n",ans);}return 0; }

回文自動(dòng)機(jī)：

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

?

總結(jié)

以上是生活随笔為你收集整理的2019ICPC(徐州) - Colorful String(哈希+二分+动态规划/回文自动机)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。