题目大意:(如题)
输入输出:(如题)
解题思路:
1.简单动态规划。
2.纠结的边界处理,不建议采用dp[i]表示s前i个字符能否取得这种方法。用这种方法实现字符串储存的时候会比较麻烦。而且如果存储不对边界处理会非常麻烦……(最先我采用的是这种方法,结果WA 4次,多次处理还是有长度为0和长度为1的情况无法分辨,最终放弃)
核心代码:

lens=s.length();
	for(i=0;i<lens;i++)
	{
		for(j=0;j<cntp;j++)
		{
			flag=false;
			len=p[j].length();
			if(i+len>lens)//如果加入这个字符串超过了s的长度则不满足条件
				continue;
			for(k=0;k<len;k++)
				if(s[i+k]!=p[j][k])//有一个字符不同不满足条件
				{
					flag=true;
					break;
				}
			if(flag==false&&len+i>maxn)//满足条件更新最大值
					maxn=len+i;
		}
		if(i+1>maxn)//结束条件
			break;
	}

发表评论

电子邮件地址不会被公开。

Post Navigation