icontofig | 发布于 2019-09-06 22:19:42 | 阅读量 359 | Trie 思维题 hash
发布于 2019-09-06 22:19:42 | Trie 思维题 hash
2018 ACM/ICPC Asia Jiaozuo Regional K.Counting Failures on a Trie  Trie 思维题 倍增 Hash
题目大意给出一棵trie树和一个字符串,然后对于每一次询问l,r,在Trie树上对子串[l,r]进行匹配。如果在某个字符处失配,则重新跳回Trie树根节点并忽略这个字符继续匹配。 求问对于每一个询问,在匹配过程中会失配几次,且最终会到达哪个节点。 题解暴力搜索必然是n^2的,对于此题1e5还有多组数据的情况想都不要想。 而每一次失配我们都会重新回到起点。 于是我们可以用预处理从每个位置的下一个位置开始的子串第一次的失配位置是在原字符串中的哪个位置。由于在这个位置我们会失配回到起点然后再次从这个位置的下一个位置开始,所以应该可以想到这个失配过程是完全可以去倍增的!。我们可以用倍增来处理失配次数,
继续阅读
icontofig | 发布于 2017-01-08 11:52:59 | 阅读量 173 | hash DP
发布于 2017-01-08 11:52:59 | hash DP
题目描述几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个,一个是星号(“*”),可以匹配0个及以上的任意字符:另一个是问号(“?”),可以匹配恰好一个任意字符。现在需要你编写一个程序,对于给定的文件名列表和一个包含通配符的字符串,判断哪些文件可以被匹配。 输入格式第一行是一个由小写字母和上述通配符组成的字符串。第二行包含一个整数n,表示文件个数。接下来n行,每行为一个仅包含小写字母字符串,表示文件名列表。 输出格式输出n行,每行为“YES”或“NO”,表示对应文件能否被通配符匹配。 样例输入*aca?ctc6acaacatctcacatctcaa
继续阅读