111qqz的小窝

老年咸鱼冲锋!

hdu 5763 || 2016 multi #4 1001 Another Meaning (kmp+dp)

hdu 5763 题目链接

题意:给定两个字符串A和B,每个出现在A中的B(可以overlap)都有两种含义,问A串一共可能有多少种含义。

思路:kmp+dp.

考虑dp[i]为前i个字符(也就是从开始长度为i,注意不是字符串的下标为i)的含义数。

我们考虑第i个字符对其他位置字符的贡献。

首先第i位的含义数可以无条件得转移到i+1位。也就是dp[i+1]+=dp[i];

此外,如果第i位是一个B串开始的位置,那么第i位对i+len2位就有贡献。也就是dp[i+len2]+=dp[i];

初始化dp[0]=1,其他为0.

剩下我们要做的就是处理出A串中的哪些位置是B串开始的位置。

kmp处理下就好,用一个布尔数组标记。

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz