BZOJ-3473 (廣義后綴自動(dòng)機(jī):拓?fù)?or 啟發(fā)式合并)

題目鏈接

題意

$n$個(gè)字符串,詢問(wèn)每個(gè)字符串一共有幾個(gè)子串至少出現(xiàn)在$n$個(gè)字符串中的$k$個(gè)

思路: 拓?fù)?/h4>

建廣義后綴自動(dòng)機(jī), $dp[i]$記錄每個(gè)節(jié)點(diǎn)表示符合條件的數(shù)量,按照拓?fù)湫蚋?span id="ze8trgl8bvbq" class="katex--inline">$dp$,然后跑這$n$個(gè)串計(jì)算答案

思路: 啟發(fā)式合并

set記錄每個(gè)節(jié)點(diǎn)在那幾個(gè)串中出現(xiàn)過(guò),在$parent$樹上$dfs$合并set,最后在跑n個(gè)串計(jì)算答案

#include <bits/stdc++.h> const int maxn = 2e5 + 5; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; struct SAM{int trans[maxn<<1][26], slink[maxn<<1], maxlen[maxn<<1];// 用來(lái)求endposint indegree[maxn<<1], endpos[maxn<<1], rank[maxn<<1], ans[maxn<<1];long sum[maxn<<1];int last, now, root, len;inline void newnode (int v) {maxlen[++now] = v;}inline void init() {root = now = 1;memset(trans, 0, sizeof(trans));}inline void extend(int c) {if (trans[last][c]) { // 廣義自動(dòng)機(jī) 節(jié)點(diǎn)合并 節(jié)省空間int p = last, np = trans[last][c];if (maxlen[last] + 1 == maxlen[np]) last = np;else {int q = trans[p][c];newnode(maxlen[p]+1);int nq = now;memcpy(trans[nq], trans[q], sizeof(trans[q]));slink[nq] = slink[q];slink[q] = last = nq;while (p && trans[p][c] == q) {trans[p][c] = nq;p = slink[p];}}return;}newnode(maxlen[last] + 1); // 新建節(jié)點(diǎn)int p = last, np = now;// 更新transwhile (p && !trans[p][c]) { // last的slink只想新節(jié)點(diǎn)trans[p][c] = np;p = slink[p];}if (!p) slink[np] = root; else { // slink中存在節(jié)點(diǎn)有到c的邊int q = trans[p][c];if (maxlen[p] + 1 != maxlen[q]) { // 判斷是否為同一個(gè)endposnewnode(maxlen[p] + 1); // 將q點(diǎn)拆出nq，使得maxlen[p] + 1 == maxlen[q]int nq = now;memcpy(trans[nq], trans[q], sizeof(trans[q]));slink[nq] = slink[q];slink[q] = slink[np] = nq;while (p && trans[p][c] == q) {trans[p][c] = nq;p = slink[p];} }else slink[np] = q;}last = np;// 初始狀態(tài)為可接受狀態(tài)endpos[np] = 1;}inline void insert(char *buf) {len = strlen(buf);last = 1;for (int i = 0; i < len; ++i) extend(buf[i] - 'a'); // extend(s[i] - '1');}int cnt[maxn], vis[maxn];long long dp[maxn];inline void Topsort() {for (int i = 1; i <= now; ++i) indegree[maxlen[i]]++;for (int i = 1; i <= now; ++i) indegree[i] += indegree[i-1];for (int i = 1; i <= now; ++i) rank[indegree[maxlen[i]]--] = i;}inline void init_string(char *buf, int num) {int tnow = 1;for (int i = 0; buf[i]; ++i) {tnow = trans[tnow][buf[i] - 'a'];int tmp = tnow;while (tmp && vis[tmp] != num) {vis[tmp] = num;cnt[tmp]++;tmp = slink[tmp];}}}inline void init_dp(int k) {Topsort();for (int i = 1; i <= now; ++i) {int tnow = rank[i];if (cnt[tnow] >= k) dp[tnow] = maxlen[tnow] - maxlen[slink[tnow]];if (slink[tnow]) dp[tnow] += dp[slink[tnow]];} }inline void solve(char *buf) {long long ans = 0;int tnow = 1;for (int i = 0; buf[i]; ++i) {tnow = trans[tnow][buf[i] - 'a'];ans += dp[tnow];}printf("%lld ", ans);} }sam; char s[maxn], t[maxn]; int pos[maxn], length[maxn]; int main() {int n, k, now = 0;scanf("%d%d", &n, &k);sam.init();for (int i = 1; i <= n; ++i) {scanf("%s", t);length[i] = strlen(t);pos[i] = now;for (int j = 0; j < length[i]; ++j) {s[now++] = t[j];}s[now++] = 0;sam.insert(s+pos[i]);}for (int i = 1; i <= n; ++i) sam.init_string(s+pos[i], i);sam.init_dp(k);for (int i = 1; i <= n; ++i) sam.solve(s+pos[i]);return 0; } #include <bits/stdc++.h> const int maxn = 2e5 + 5; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; struct SAM{int trans[maxn<<1][26], slink[maxn<<1], maxlen[maxn<<1];// 用來(lái)求endposint indegree[maxn<<1], endpos[maxn<<1], rank[maxn<<1], ans[maxn<<1];set<int> st[maxn<<1];vector<int> g[maxn<<1];int last, now, root, len;inline void newnode (int v) {maxlen[++now] = v;}inline void init() {root = now = 1;memset(trans, 0, sizeof(trans));}inline void extend(int c, int num) {if (trans[last][c]) { // 廣義自動(dòng)機(jī) 節(jié)點(diǎn)合并 節(jié)省空間int p = last, np = trans[last][c];if (maxlen[last] + 1 == maxlen[np]) {last = np;st[last].insert(num); // 插入新的字符標(biāo)記} else {int q = trans[p][c];newnode(maxlen[p]+1);int nq = now;memcpy(trans[nq], trans[q], sizeof(trans[q]));slink[nq] = slink[q];slink[q] = last = nq;st[last].insert(num); // 插入新的字符標(biāo)記while (p && trans[p][c] == q) {trans[p][c] = nq;p = slink[p];}}return;}newnode(maxlen[last] + 1); // 新建節(jié)點(diǎn)int p = last, np = now;// 更新transwhile (p && !trans[p][c]) { // last的slink只想新節(jié)點(diǎn)trans[p][c] = np;p = slink[p];}if (!p) slink[np] = root; else { // slink中存在節(jié)點(diǎn)有到c的邊int q = trans[p][c];if (maxlen[p] + 1 != maxlen[q]) { // 判斷是否為同一個(gè)endposnewnode(maxlen[p] + 1); // 將q點(diǎn)拆出nq，使得maxlen[p] + 1 == maxlen[q]int nq = now;memcpy(trans[nq], trans[q], sizeof(trans[q]));slink[nq] = slink[q];slink[q] = slink[np] = nq;while (p && trans[p][c] == q) {trans[p][c] = nq;p = slink[p];} }else slink[np] = q;}last = np;st[last].insert(num); // 插入新的字符標(biāo)記}inline void insert(char *buf, int num) {len = strlen(buf);last = 1;for (int i = 0; i < len; ++i) extend(buf[i] - 'a', num); // extend(s[i] - '1');}int cnt[maxn<<1];inline void get_parent() { // parent樹for (int i = 1; i <= now; ++i) {if (slink[i]) g[slink[i]].push_back(i);}}inline void dfs(int u) { // 更新每個(gè)節(jié)點(diǎn)被幾個(gè)字符串經(jīng)過(guò)for (auto v : g[u]) {dfs(v);if (st[u].size() < st[v].size()) swap(st[u], st[v]);for (auto it : st[v]) st[u].insert(it);}cnt[u] = st[u].size();}inline void solve(char *buf, int k) {long long ans = 0;int tnow = 1;for (int i = 0; buf[i]; ++i) {while (tnow && trans[tnow][buf[i] - 'a'] == 0) tnow = slink[tnow];tnow = trans[tnow][buf[i] - 'a'];while (tnow && cnt[tnow] < k) tnow = slink[tnow];if (cnt[tnow] >= k) ans += maxlen[tnow];}printf("%lld ", ans);} }sam; char s[maxn], t[maxn]; int pos[maxn], length[maxn]; int main() {int n, k, now = 0;scanf("%d%d", &n, &k);sam.init();for (int i = 1; i <= n; ++i) {scanf("%s", t);length[i] = strlen(t);pos[i] = now;for (int j = 0; j < length[i]; ++j) {s[now++] = t[j];}s[now++] = 0;sam.insert(s+pos[i], i);}sam.get_parent();sam.dfs(1);for (int i = 1; i <= n; ++i) sam.solve(s+pos[i], k);return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ-3473 (广义后缀自动机:拓扑 or 启发式合并)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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