(2016多校联赛)hdu 5763 Another Meaning

科技前沿 • 2025-02-06 07:29 • 阅读 36

大家好，我是讯享网，很高兴认识大家。

题目链接：

题目大意：

给你两个字符串a，b，其中b字符串有两种意思，a串中也许有包含b串，问a串总共能组合出几种意思。

解题思路：

很明确的，这种题可以用DP。

我们令dp[i]为第i位之前的串共有多少种意思，这样答案输出 dp[ a串的长度 ] 即可。

讯享网

首先，到第i位为止，不管有没有多种意思，至少dp[i] = dp[i-1]。

然后再判断，如果从第 i-len2 位到第 i-1 位（len2为b串长度）的字符串正好为有两种意思的b串，那么

dp[i] = dp[i] + dp[i-len2]

因为对于每一个i位之前的串来说，若它的末尾len2长度的串有两种意思（第一种意思已经dp[i]=dp[i-1]了），多出来的一种意思需要和i-len2之前的串的每种意思组合一次，所以需要i-len2之前的意思数加上原意的意思数。加完记得取模。

题解有说到要用kmp或者hash来串匹配末尾len2长度的字符串，但是好像直接使用substr函数得出的字符串与b串判断也是可以过的。。。感觉时间复杂度差的不多。可能数据卡的不严吧。

代码如下：

#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <math.h> #include <stdio.h> #include <string.h> #include <map> using namespace std; const int maxn=; long long int dp[maxn]; int main() { int t,len1,len2,x=1; string str1,str2; cin>>t; while(t--) { cin>>str1>>str2; len1=str1.length(); len2=str2.length(); for (int i=0; i<len2; i++) dp[i]=1; for(int i=len2;i<=len1;i++) { dp[i]=dp[i-1]; string a=str1.substr(i-len2,len2); if(a==str2) { dp[i]=dp[i]+dp[i-len2]; } dp[i] %=; } cout<<"Case #"<<x<<": "<<dp[len1]<<endl; x++; } return 0; }

讯享网

(2016多校联赛)hdu 5763 Another Meaning

相关推荐