[数据结构与算法]蓝肽子序列 [蓝桥杯]

蓝肽子序列，一个对 最长公共子序列 改版的题目。

原题传送

分析： 这是最长公共子序列的升级版，在最长公共子序列中是以一个 字符 为单位，现在是以一个 单词 为单位，我们可以把一个单词看作一个字符来处理。
最长公共子序列中每次都是对某个字符进行比较，这道题中我们要取出两个字符串的一个完整的单词去进行比较。
dp[i][j]：表示第一个字符串在i位置时，第二个字符串在j位置时，他们公共单词的最大个数。
状态转移这里不好描述，见代码及注释。

#include<bits/stdc++.h>
using namespace std;
string s11,s22 ,s1 ,s2;
int dp[1010][1010];
int main(){
	cin>>s1>>s2;
	int size1; 
	int size2; 
	size1 = s1.size();
	size2 = s2.size();
	string son1, son2;
//	最最长公共子序列的升级版，之前是以一个 字符 为单位，现在是以一个 单词 为单位。 
//	针对每一次的统计，都要先取出一个完整的单词去统计。 
	for(int i = 0; i < size1;){
		son1 += s1[i];i++;
		 while(i < size1 &&!(s1[i]<='Z' && s1[i]>='A')){ //取出一个   蓝太子
		 	son1 += s1[i];
		 	++i;
		 }
		for(int j = 0; j < size2; ){
			son2 += s2[j];j++;
			while(j < size2 &&!(s2[j]<='Z' && s2[j]>='A')){  //取出一个  蓝太子
		 		son2 += s2[j];
		 		++j;
		 	}
		 	
		 	 //  下面就是和最长公共子序列一样的dp思路。 
			if(son1.compare(son2) == 0){   //两个  蓝太子（字符） 相等 
			  // 那么公共蓝肽子序列 + 1。
				dp[i][j] = dp[i-son1.size()][j-son2.size()] + 1;
			}else{       //    两个  蓝太子（字符） 不等
			// 那么取 最大的那一个 作为后面计算的状态。  
				dp[i][j] = max(dp[i-son1.size()][j], dp[i][j-son2.size()]);
				
			}
			son2.clear();  //注意要  清零  取出的兰太子，以免影响下一次计算 
		}
		son1.clear();
	}
	cout<<dp[size1][size2];
	return 0;
}