題目描述

給出\(n\)個(gè)串，你要從每個(gè)串中抽出一個(gè)子串（可以是空串），把他們拼接起來，問：

按字典序輸出所有可能的結(jié)果（包括空串）

輸出總共有多少種不同的結(jié)果（包括空串），對\(1e9+7\)取模

最后輸入一個(gè)\(k\)，為\(0\)時(shí)只回答第二問，為\(1\)時(shí)回答兩個(gè)問

保證輸入不超過\(1MB\)，輸出不超過\(200MB\)（就是說第二問真實(shí)值很大時(shí)不會(huì)要求回答第一問）

解析

要取出子串，容易想到后綴自動(dòng)機(jī)

于是對每個(gè)串建出后綴自動(dòng)機(jī)

然后考慮怎么表示“拼接”

不難發(fā)現(xiàn)，如果后面某個(gè)串中存在的字符可以在當(dāng)前這個(gè)自動(dòng)機(jī)內(nèi)轉(zhuǎn)移到，那么取后者不會(huì)漏掉任何結(jié)果，所以我們只用管每個(gè)節(jié)點(diǎn)在自己的自動(dòng)機(jī)內(nèi)轉(zhuǎn)移不到的字符

即只有當(dāng)不能在自己的串中轉(zhuǎn)移時(shí)才考慮拼接后面的串

假設(shè)某個(gè)節(jié)點(diǎn)\(u\)沒有轉(zhuǎn)移到\(c\)的邊，那么我們找到它后面的自動(dòng)機(jī)中第一個(gè)能轉(zhuǎn)移到\(c\)的根節(jié)點(diǎn)\(rt\)，從\(u\)到\(rt->trans[c]\)拉一條邊，這樣就表示了“拼接”的過程

第一問就從第一個(gè)串的根節(jié)點(diǎn)開始貪心地\(dfs\)，過程中輸出即可，此處可以信仰一波不會(huì)\(TLE\)，不然光輸出就\(GG\)了，想來不會(huì)有這種數(shù)據(jù)……

第二問就是問路徑數(shù)了，拓?fù)渑判?span id="ze8trgl8bvbq" class="math inline">\(dp\)即可

代碼

為什么貼的是\(70pts\)代碼呢？因?yàn)橛?span id="ze8trgl8bvbq" class="math inline">\(3\)組數(shù)據(jù)輸出實(shí)在太長，\(OJ\)判了所有人\(OLE\)……

#include <cstdio> #include <iostream> #include <queue> #include <cstring> #include <algorithm> #define MAXN 1000005typedef long long LL; const int mod = (int)1e9 + 7; const char set[] = {'A', 'C', 'G', 'T'}; struct SAM {int idx, cnt, last, root[MAXN], next[MAXN << 1][4], link[MAXN << 1], maxlen[MAXN << 1], deg[MAXN << 1], top, dp[MAXN << 1];bool vis[MAXN << 1]; char cur[MAXN << 1];int newnode(int = 0);int add(int);void insert(char *);void prework();void prework(int, int);void dfs(int);void bfs(); };int N, K; char str[MAXN]; SAM sam; int ans;inline void inc(int &x, int y) { x += y; if (x >= mod) x -= mod; } inline void dec(int &x, int y) { x -= y; if (x < 0) x += mod; } inline int add(int x, int y) { x += y; return x >= mod ? x - mod : x; } inline int sub(int x, int y) { x -= y; return x < 0 ? x + mod : x; }int main() {freopen("copy.in", "r", stdin);freopen("copy.out", "w", stdout);scanf("%d", &N);for (int i = 1; i <= N; ++i) {scanf("%s", str);sam.insert(str);}scanf("%d", &K);sam.prework();if (K) sam.dfs(sam.root[1]);sam.bfs();printf("%d\n", ans);return 0; } int SAM::newnode(int x) {++idx;if (x) {link[idx] = link[x], maxlen[idx] = maxlen[x];for (int i = 0; i < 4; ++i) next[idx][i] = next[x][i];}return idx; } int SAM::add(int c) {int np = newnode(), p = last;maxlen[np] = maxlen[last] + 1;while (p && !next[p][c]) next[p][c] = np, p = link[p];if (!p) link[np] = root[cnt];else {int q = next[p][c];if (maxlen[q] == maxlen[p] + 1) link[np] = q;else {int nq = newnode(q);maxlen[nq] = maxlen[p] + 1;link[q] = link[np] = nq;while (p && next[p][c] == q) next[p][c] = nq, p = link[p];}}return np; } void SAM::insert(char *s) {int n = strlen(s); last = root[++cnt] = newnode();for (int i = 0; i < n; ++i) last = add(std::lower_bound(set, set + 4, s[i]) - set); } void SAM::prework() {for (int i = cnt; i; --i) prework(root[i], root[i + 1]);for (int i = 1; i <= idx; ++i) for (int j = 0; j < 4; ++j) ++deg[next[i][j]];for (int i = 2; i <= cnt; ++i) for (int j = 0; j < 4; ++j) --deg[next[root[i]][j]]; } void SAM::prework(int x, int y) {if (vis[x]) return;vis[x] = 1;for (int i = 0; i < 4; ++i)if (!next[x][i]) next[x][i] = next[y][i];else prework(next[x][i], y); } void SAM::dfs(int x) {cur[top] = '\0';printf("%s\n", cur);for (int i = 0; i < 4; ++i)if (next[x][i]) {cur[top++] = set[i];dfs(next[x][i]);--top;} } void SAM::bfs() {static int q[MAXN << 1], hd, tl;q[tl++] = root[1], dp[root[1]] = 1;while (hd < tl) {int p = q[hd++];if (!p) continue;inc(ans, dp[p]);for (int i = 0; i < 4; ++i) {inc(dp[next[p][i]], dp[p]);if (!(--deg[next[p][i]])) q[tl++] = next[p][i];}} } //Rhein_E 70pts

轉(zhuǎn)載于:https://www.cnblogs.com/Rhein-E/p/10560540.html

總結(jié)

以上是生活随笔為你收集整理的day16T2改错记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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