- #include < bits / stdc++.h > using namespace std;
- typedef long long ll;
- const int N = 12;
- const int MAXN = 600010;
- int num,
- ans[10020],
- nn;
- bool vis[600010];
- bool flag = false;
- struct Trie { //数组形式
- int Next[MAXN][N],
- Fail[MAXN],
- End[MAXN],
- root,
- tot; //大小为所以匹配字符串的总和
- int newnode() { //结构体内部用
- for (int i = 0; i < N; i++) Next[tot][i] = -1;
- End[tot++] = 0;
- return tot - 1;
- }
- void init() {
- tot = 0;
- root = newnode();
- }
- void insert(char buf[], int x) {
- int len = strlen(buf);
- int now = root; //now是temp指针
- for (int i = 0; i < len; i++) {
- int k = buf[i] - ‘0‘;
- if (Next[now][k] == -1) Next[now][k] = newnode(); //next数组代表的是下一个字符索引
- now = Next[now][k];
- }
- End[now] = x; //end数组是当前字符串的个数.字典中可能有相同的单词,若只算一次,改为1.
- }
- void build() { //构造fail指针,后缀是某些前缀
- queue < int > que;
- Fail[root] = root;
- for (int i = 0; i < N; i++) {
- if (Next[root][i] == -1) Next[root][i] = root;
- else {
- Fail[Next[root][i]] = root;
- que.push(Next[root][i]);
- }
- }
- while (!que.empty()) { //bfs,会将所有的匹配子串都遍历到
- int now = que.front();
- que.pop();
- for (int i = 0; i < N; i++) {
- if (Next[now][i] == -1) Next[now][i] = Next[Fail[now]][i];
- else {
- Fail[Next[now][i]] = Next[Fail[now]][i]; //fail指向最长的
- que.push(Next[now][i]);
- }
- }
- }
- }
- void query(char buf[]) {
- int len = strlen(buf),
- now = root;
- for (int i = 0; i < len; i++) {
- now = Next[now][buf[i] - ‘0‘];
- int temp = now;
- while (temp != root) {
- if (End[temp] && !vis[temp]) ans[nn++] = End[temp],
- vis[temp] = true,
- flag = true;
- temp = Fail[temp];
- }
- }
- }
- };
- Trie ac;
- char buf[60004],
- buf2[60004],
- tmp[6002];
- int n,
- m;
- int main() {
- while (scanf("%d%d", &m, &n) != EOF) {
- memset(ans, 0, sizeof ans);
- memset(vis, 0, sizeof vis);
- nn = 0;
- ac.init();
- int t = 0;
- flag = false;
- for (int i = 1; i <= m; i++) {
- scanf("%s", tmp);
- strcat(buf, tmp);
- }
- for (int i = 1; i <= n; i++) {
- scanf("%*s %*s %d] %s", &num, buf2);
- ac.insert(buf2, num);
- }
- ac.build(); //不要忘记build
- ac.query(buf);
- if (flag) {
- printf("Found key:");
- for (int i = 0; i < nn; i++) {
- printf(" [Key No. %d]", ans[i]);
- }
- printf("\n");
- } else printf("No key can be found !\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2303552.html