[BZOJ3507/Luogu3167][CQOI2014]通配符匹配(Hash,动态规划)

发布于 2018-03-20  142 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3507/Luogu3167][CQOI2014]通配符匹配(Hash,动态规划)

Description

几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个,一个是星号(“”’),可以匹配0个及以上的任意字符:另一个是问号(“?”),可以匹配恰好一个任意字符。现在需要你编写一个程序,对于给定的文件名列表和一个包含通配符的字符串,判断哪些文件可以被匹配。

Tag

Hash,动态规划

解决思路

题意看起来很像一个“模糊”匹配的AC自动机,但是,由于直接模糊匹配需要同时在AC自动机上走若干个节点,复杂度无法保证。
分别处理每一个询问,把通配串中的所有通配符提取出来,设F[i][j]表示第i个通配符能否匹配字符串中的第j个字符。那么,若有F[i][j],F[i+1][j+len]成立的条件是通配串中从第i个通配符到第i+1个通配符之间的字符能与需要匹配的字符串的从j开始对应长度的字符串相匹配(设这个长度为len),这个可以用字符串Hash来做。
而至于*和?的分别处理,由于*可以匹配从0开始的任意长度,所以转移到[j+len],然后再一直向后转移;而?只能匹配一个,所以必须强制转移到[j+len+1]。
为了方便在最后统计处理,可以在通配串的最后加一个?,在询问串的最后加一个与字符集无关的字符#,这样就只要判断最后两个能否匹配了。
为了方便,这里使用自然溢出的Hash方法。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3507/Luogu3167][CQOI2014]通配符匹配(Hash,动态规划)


HNCJ OIer