鏈接：https://ac.nowcoder.com/acm/contest/884/I

?

題意：求string串有多少個本質不同的子串，且這些子串之間兩兩不存在 a==rev(a），即不存在長度1以上的回文串

題解：

要算string 和 rev(string)的所有子串，對string

和rev(string）建立廣義后綴自動機，則理論上所有子串增加了一倍，但實際回文串和 不是回文但a == rev(a）的串沒有增加，

比如 aba子串ab和ba。則我們計算出此時不同串個數 ans1, 再計算出string串中回文串數 ans2，則(ans1+ans2)/2即為所求.

?

#include<bits/stdc++.h>using namespace std; typedef long long LL;const int maxn = 2*1e6+5; const int maxc = 28;char str[maxn];struct SMA{int len[maxn * 2];int link[maxn * 2];int cnt[maxn * 2];int nxt[maxn * 2][maxc];int idx;int last;LL epos[maxn * 2];LL a[maxn];void init(){last = idx = 1;link[1] = len[1] = 0;}//SMA建圖void SMA_Extend(int c){int x = ++idx;len[x] = len[last] + 1;epos[x] = 1;int p;for(p = last; p && !nxt[p][c]; p = link[p]) nxt[p][c] = x;if(!p) link[x] = 1, cnt[1]++;else{int q = nxt[p][c]; //p通過c轉移到的節點if(len[p] + 1 == len[q]) //pq是連續的link[x] = q, cnt[q]++; //將新節點后綴連接指向q即可，q節點的被后綴連接數+1else{int nq = ++idx; //不連接，需要復制一份q節點len[nq] = len[p] + 1; //令nq與p連接link[nq] = link[q]; //因后面link[q]改變此處不加cntmemcpy(nxt[nq], nxt[q], sizeof(nxt[q])); //復制q的信息給nqfor(; p && nxt[p][c] == q; p = link[p])nxt[p][c] = nq; //沿著后綴連接，將所有通過c轉移為qlink[q] = link[x] = nq; //將x和q后綴連接改為nqcnt[nq] += 2; //nq增加兩個后綴連接}}last = x;}//求不相同子串數量LL getSubNum(){LL ans = 0;for(int i = 2; i <= idx; i++) ans += len[i] - len[link[i]];return ans;} }sma;struct PAM{int nxt[maxn][maxc];int fail[maxn];int cnt[maxn];int len[maxn];int S[maxn];int last, n, p;int Create(int rt){for(int i = 0; i <= 26; i++) nxt[p][i] = 0;cnt[p] = 0;len[p] = rt;return p++;}void init(){p = last = n = 0;Create(0);Create(-1);S[n] = -1;fail[0] = 1;}int getFail(int x){while(S[n-len[x]-1] != S[n]) x = fail[x];return x;}void Insert(int c){S[++n] = c;int cur = getFail(last);if(!nxt[cur][c]){int now = Create(len[cur] + 2);fail[now] = nxt[getFail(fail[cur])][c];nxt[cur][c] = now;//num[now] = num[fail[now]] + 1;}last = nxt[cur][c];cnt[last]++;} }pam;int main() {scanf("%s", str);int len = strlen(str);sma.init();for(int i = 0; i < len; i++) sma.SMA_Extend(str[i] - 'a');sma.last = 1;for(int i = len-1; i >= 0; i--) sma.SMA_Extend(str[i] - 'a');LL ans1 = sma.getSubNum();pam.init();for(int i = 0; i < len; i++){//printf("fdsjfkds\n");pam.Insert(str[i] - 'a');}//printf(" %d %d\n", pam.p-2, ans1);printf("%lld\n", (ans1 + pam.p - 2) / 2);return 0; }

?

總結

以上是生活随笔為你收集整理的2019牛客第四场I题 string的全部內容，希望文章能夠幫你解決所遇到的問題。

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