題意

題目鏈接

Sol

直接在SAM上亂搞

枚舉前綴，用SAM統計可以匹配的后綴，具體在匹配的時候維護和當前節點能匹配的最大值

然后再把parent樹上的點的貢獻也統計上，這部分可以爆跳parent樹(假的，因為這題數據隨機)，也可以直接樹形dp一波記下每個點被統計的次數

#include<bits/stdc++.h> #define LL long long using namespace std; const int MAXN = 4e5 + 10; int N1, N2; char a[MAXN], b[MAXN]; // struct SAM {int fa[MAXN], ch[MAXN][26], len[MAXN], siz[MAXN], tot, las, root, f[MAXN], g[MAXN];vector<int> v[MAXN];// SAM() {// root = las = tot = 1;// }void insert(int x) {int now = ++tot, pre = las; las = now; siz[now] = 1;len[now] = len[pre] + 1;for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now;if(!pre) fa[now] = root;else {int q = ch[pre][x];if(len[pre] + 1 == len[q]) fa[now] = q;else {int ns = ++tot; fa[ns] = fa[q]; len[ns] = len[pre] + 1;memcpy(ch[ns], ch[q], sizeof(ch[q]));fa[q] = fa[now] = ns;for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = ns;}}}void Build() {for(int i = 2; i <= tot; i++) v[fa[i]].push_back(i);}void dfs(int x, int opt) {for(int i = 0; i < v[x].size(); i++) {int to = v[x][i];dfs(to, opt); if(opt == 1) siz[x] += siz[to]; if(opt == 2) f[x] += f[to] + g[to];}} // }sam; int main() {root = las = tot = 1;scanf("%s%s", a + 1, b + 1);N1 = strlen(a + 1); N2 = strlen(b + 1);for(int i = 1; i <= N1; i++) insert(a[i] - 'a');Build(); dfs(root, 1);int now = root, cur = 0; LL ans = 0;for(int i = 1; i <= N2; i++) {int x = b[i] - 'a';if(ch[now][x]) now = ch[now][x], cur++;else {while(!ch[now][x] && now) now = fa[now];if(!now) now = 1, cur = 0;else cur = len[now] + 1, now = ch[now][x];}ans += 1ll * (cur - len[fa[now]]) * siz[now];g[now]++;//int tmp = fa[now];//while(tmp != 1) ans += (len[tmp] - len[fa[tmp]]) * siz[tmp], tmp = fa[tmp];}dfs(root, 2);for(int i = 1; i <= tot; i++) ans += 1ll * (len[i] - len[fa[i]]) * siz[i] * f[i];cout << ans;return 0; } /* aa aaacb abcababababba abbababab */

總結

以上是生活随笔為你收集整理的BZOJ4566: [Haoi2016]找相同字符(后缀自动机)的全部內容，希望文章能夠幫你解決所遇到的問題。

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