原题链接：信息学奥赛一本通T1667-巧克力棒
解题思路:
AC自动机。使用栈保存匹配过程中的信息，若匹配成功弹出模式串，最后栈剩下的就是匹配完剩下的字符。
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | constexpr auto Inf = 0X3F3F3F3F;#ifndef LOCAL #include <bits/stdc++.h>#endiftypedef unsigned long long LL;using namespace std;namespace IO { inline LL read() { LL o = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); } return o * f; } inline char recd() { char o; while ((o = getchar()) < '0' || o > '9'); return o; } inline double reod() { double o = read(), f = 1; char c; while ((c = getchar()) > '/' && c < ':') o += (c - '0') / (f *= 10); return o; }}using namespace IO;const int SIZE = 1E5 + 7, Mod = (1E9 + 7, 998244353);struct Aho { struct Node { int sub[26]; int fail, g; } Node[SIZE << 2]; int Ind; void clear() { for (int pos = 0; pos <= Ind; pos++) { for (int e = 0; e < 26; e++) Node[pos].sub[e] = 0; Node[pos].fail = Node[pos].g = 0; } Ind = 0; } int Ins(char S[], int g) { int now = 0; for (int pos = 1; S[pos]; pos++) { if (!Node[now].sub[S[pos] - 'a']) Node[now].sub[S[pos] - 'a'] = ++Ind; now = Node[now].sub[S[pos] - 'a']; } Node[now].g = g; return now; } void BUILD() { queue<int> que; for (int pos = 0; pos < 26; pos++) if (Node[0].sub[pos]) Node[Node[0].sub[pos]].fail = 0, que.push(Node[0].sub[pos]); while (!que.empty()) { int now = que.front(); que.pop(); for (int pos = 0; pos < 26; pos++) { if (Node[now].sub[pos]) Node[Node[now].sub[pos]].fail = Node[Node[now].fail].sub[pos], que.push(Node[now].sub[pos]); else Node[now].sub[pos] = Node[Node[now].fail].sub[pos]; } } } } Aho;char T[SIZE], S[SIZE]; int stacks[SIZE], top, back[SIZE];int main() { scanf("%s", T + 1); int N = read(); for (int pos = 1; pos <= N; pos++) scanf("%s", S + 1), Aho.Ins(S, strlen(S + 1)); Aho.BUILD(); int now = 0; for (int pos = 1; T[pos]; pos++) { now = Aho.Node[now].sub[T[pos] - 'a']; back[pos] = now, stacks[++top] = pos; if (Aho.Node[now].g) { top -= Aho.Node[now].g; now = back[stacks[top]]; } } for (int pos = 1; pos <= top; pos++) printf("%c", T[stacks[pos]]);} |
6.6 分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复