去年大连的一个题目,当时现场赛的时候就没做出来。赛后出题人说是“经典”的shift-and算法(经典个jb啊?),不过到现在才补,也是挺菜的。
例题是hdu 5972

给一个长度为n的模式子串,子串的每个位置分别可以是一些数字,即一个位置可以被多个数字匹配。再给定一个母串,问子串可以在哪些位置和木串匹配,并且输出匹配成功后的所有子串。

这个shift-and其实还是挺简单的,就是搞一个01串,代表之前多少个已经匹配啦,该匹配哪一个啦。然后预处理一个东西,表示这个字符可以匹配这个位置,然后两个东西直接and一下,如果两个可以匹配的话,那就是1,其中一个不行的话就是0。正常的字符串子串的复杂度是\(O(N*M)\)的,这个的话,时间复杂度可以除个64,是一个bitset的一个很好的用法。

发表评论

电子邮件地址不会被公开。 必填项已用*标注