骨牌铺方格 http://acm.hdu.edu.cn/showproblem.php?pid=2046 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description 在2×n的一个长方形方格中,用一个1×
题目大意 给出 n n个模式串和一个串SS,用这 n n个模式串尽量多的覆盖SS,模式串之间可以重叠,求出最少有多少个位置没有被覆盖。 解法 这题有许多解法,下面列举两种: 1. 将所有模式串和要匹配的串 S S反过来,然后做一次SASA(后缀数组),然后,肆意恶搞。 2. 对 S S做SASA,然后对于每一个匹配串都查找一下它在 S S中可能的位置,标记一下,然后,肆意恶搞。我想讲的解