題目鏈接：點擊查看

題目大意：給出一個字符串 s ，接下來給出 m 個查詢，每次查詢的形式會給出一個 l 和 r ，問區(qū)間 [ l , r ] 內(nèi)有多少個本質(zhì)不同的回文子串

題目分析：因為查詢的次數(shù)比較多，所以我們可以預(yù)處理出答案然后O(1)回答，因為回文自動機的時間復(fù)雜度為O(n)級別的，我們可以枚舉 n * n 個子串依次記錄答案

2020.11.11更新：

然后發(fā)現(xiàn)哈希也能亂搞，原理就是將每個字符串用哈希映射成不同的數(shù)字，然后就轉(zhuǎn)換成 “區(qū)間內(nèi)不同數(shù)字的個數(shù)” 了，用樹狀數(shù)組或線段樹離線隨便做就好了

如果用 map 記錄哈希的話，時間復(fù)雜度就是 O( n * n * logn + q * logn )

悄咪咪的說一句，打算在校賽上放這個題，因為哈希亂搞也是可以搞過去的嘛。。

代碼：

回文自動機

#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=1e3+100;char s[N];int n,ans[N][N];struct Palindrome_tree {int nxt[N][26];int fail[N]; // 當前節(jié)點最長回文后綴的節(jié)點int len[N]; // 當前節(jié)點表示的回文串的長度int cnt[N]; // 當前節(jié)點回文串的個數(shù)， 在getcnt后可得到全部int sed[N]; // 以當前節(jié)點為后綴的回文串的個數(shù)（并不是表示第i結(jié)尾的回文串的種類數(shù)，如果要求每個點結(jié)尾的數(shù)的回文串個數(shù)，得用last）int record[N]; //record記錄了節(jié)點回文串的結(jié)束位置char s[N];int tot; // 節(jié)點個數(shù)int last; // 上一個節(jié)點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為偶數(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é)點回文串新建兩端是否相等//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個字符可以加到哪個節(jié)點的兩端形成回文串if (!nxt[p][c]){tot++;len[tot] = len[p] + 2; // 在p節(jié)點兩端添加兩個字符fail[tot] = nxt[getfail(fail[p], n)][c]; //tot點的后綴回文，可以由上一個節(jié)點的后綴回文嘗試得到sed[tot] = sed[fail[tot]] + 1; // 以當前節(jié)點為結(jié)尾的回文串個數(shù)nxt[p][c] = tot; // 新建節(jié)點}last = nxt[p][c]; // 當前節(jié)點成為上一個節(jié)點cnt[last]++; //當前節(jié)點回文串++record[last] = n;}void get_cnt(){for (int i = tot; i > 0; i--)cnt[fail[i]] += cnt[i];//fail[i] 的節(jié)點 為 i 節(jié)點的后綴回文串， 所以個數(shù)相加} }tree;void init() {for(int i=0;i<n;i++){tree.init();tree.build();for(int j=i;j<n;j++){tree.insert(s[j]);ans[i][j]=tree.tot-1;}} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%s",s);n=strlen(s);init();int m;scanf("%d",&m);while(m--){int l,r;scanf("%d%d",&l,&r);printf("%d\n",ans[l-1][r-1]);}}return 0; }

哈希+樹狀數(shù)組：

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #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> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;char s[N];int ans[N],c[N],n,m;vector<pair<int,int>>q[N];map<ull,int>mp;ull Hash1[N],Hash2[N],p[N];void HASH() {Hash1[0]=0,p[0]=1;for(int i=1;i<=n;i++){Hash1[i]=Hash1[i-1]*131+(s[i]-'a'+1);p[i]=p[i-1]*131;}Hash2[n+1]=0;for(int i=n;i>=1;i--)Hash2[i]=Hash2[i+1]*131+(s[i]-'a'+1); }ull get_hash1(int l,int r) {return Hash1[r]-Hash1[l-1]*p[r-l+1]; }ull get_hash2(int l,int r) {return Hash2[l]-Hash2[r+1]*p[r-l+1]; }int lowbit(int x) {return x&(-x); }void add(int x,int val) {for(int i=x;i<=n;i+=lowbit(i))c[i]+=val; }int ask(int x) {int ans=0;for(int i=x;i>0;i-=lowbit(i))ans+=c[i];return ans; }void init(int n) {for(int i=1;i<=n;i++)q[i].clear();HASH();memset(c,0,sizeof(int)*(n+5));mp.clear(); }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%s",s+1);n=strlen(s+1);init(n);scanf("%d",&m);for(int i=1;i<=m;i++){int l,r;scanf("%d%d",&l,&r);q[r].push_back({l,i});}for(int r=1;r<=n;r++){for(int l=1;l<=r;l++){if(get_hash1(l,r)==get_hash2(l,r)){if(mp[get_hash1(l,r)])add(mp[get_hash1(l,r)],-1);add(l,1);mp[get_hash1(l,r)]=l;}}for(auto it:q[r])ans[it.second]=ask(n)-ask(it.first-1);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 5658 CA Loves Palindromic(回文自动机/哈希+树状数组)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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