Untitled
unknown
plain_text
a year ago
1.3 kB
6
Indexable
#include <cstdio> #include <cstdlib> #include <cstring> const int SIGMA = 26; struct node { int len; bool end; node *suff, *link[SIGMA]; node (int l) { len = l; suff = 0; end = 0; memset(link, 0, sizeof link); } } root(0), *last = &root; void add_char(int C) { node *newl = new node(last->len + 1); node *v = last; for (; v && !v->link[C]; v = v->suff) v->link[C] = newl; if (v) { node *q = v->link[C]; if (q->len == v->len + 1) newl->suff = q; else { node *clone = new node(v->len + 1); memcpy(clone->link, q->link, sizeof q->link); clone->suff = q->suff; for (; v && v->link[C] == q; v = v->suff) v->link[C] = clone; q->suff = newl->suff = clone; } } else newl->suff = &root; last = newl; } inline int conv(char c) { if (c < 'a') return c - 'A'; return c - 'a'; } void add_string(char *s, int len) { for (int i = 0; i < len; i++) add_char(conv(s[i])); } void mark() { for (node *v = last; v; v = v->suff) v->end = 1; } char cmd[3], s[1000000]; int n; int main() { while (scanf("%s%s", cmd, s) == 2) { if (cmd[0] == 'A') add_string(s, strlen(s)); else { bool ok = 1; n = strlen(s); node *v = &root; for (int i = 0; i < n && ok; i++) if (!v->link[conv(s[i])]) ok = 0; else v = v->link[conv(s[i])]; puts(ok ? "YES" : "NO"); } } return 0; }
Editor is loading...
Leave a Comment