【UOJ #13】【UER #1】跳蚤OS

http://uoj.ac/problem/13

建立trie树，然后建立go指针，

和AC自动机里的fail指针差不多，

走到一个快捷方式就从go指针走。

注意在trie树上要保留字符'/'，不能用end标记来标识一个字符串的结束。

因为可能出现"/Iam/zz"和"/Iamzz"这两种情况，如果只用end标记，tire树上这两个字符串就会共用一条路径。

(总之是蒟蒻才会犯的错误，神犇们勿喷_(:з」∠)_)

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int in() {

	int k = 0; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar());

	for(; c >= '0' && c <= '9'; c = getchar())

		k = k * 10 + c - 48;

	return k;

}

struct State {

	int num;

	State *nxt[27], *go, *fa;

	State(State *_fa, int _num) {

		memset(nxt, 0, sizeof(nxt));

		go = 0; fa = _fa; num = _num;

	}

} *root;

State *to(char *c) {

	int len = strlen(c), x;

	if (len == 1 && c[0] == '/') return root;

	State *tmp = root;

	for(int i = 0; i < len; ++i) {

		if (c[i] == '/') x = 26;

		else x = c[i] - 'a';

		if (tmp->nxt[x] == 0)

			tmp->nxt[x] = new State(tmp, x);

		tmp = tmp->nxt[x];

		if ((c[i + 1] == '\0' || c[i + 1] == '/') && tmp->go)

			tmp = tmp->go;

	}

	return tmp;

}

char s[500003], t[500003];

void print(State *tmp) {

	int tot = 0;

	if (tmp == root) {puts("/"); return;}

	while (tmp != root) {

		if (tmp->num <= 25) t[++tot] = 'a' + tmp->num;

		else t[++tot] = '/';

		tmp = tmp->fa;

	}

	while (tot) putchar(t[tot--]);

	puts("");

}

int n, m;

int main() {

	root = new State(0, 0);

	n = in(); m = in();

	for(int i = 1; i <= n; ++i) {

		scanf("%s", s); scanf("%s", t);

		to(s)->go = to(t);

	}

	for(int i = 1; i <= m; ++i) {

		scanf("%s", s);

		print(to(s));

	}

	return 0;

}

巴特西

【UOJ #13】【UER #1】跳蚤OS

最新文章

热门文章