N个字符串

理论知识：

二进制模拟串实现暴力破解——暴力枚举出（最长）公共子序列

代码实现：

#include <iostream>
#include <string>
#include <ctime>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

// 判断字符串subSeq中的每一个字符在字符串str中的出现顺序是否为递增
bool isSubsequence(const string& str, const string& subSeq) {
	int index = -1; //设为-1而不是0，因为后边还要 +1;
	for (char ch : subSeq) {
		index = str.find_first_of(ch, index + 1); // 起始位置得是下一位，故需要 +1;
		if (index == str.npos) {
			return false;
		}
	}
	return true;
}
// 多串的公共子序列判断;
bool isComSeq(const vector<string>& vs, const string& subseq) {
	for (string str : vs) {
		if (!isSubsequence(str, subseq)) {
			return false;
		}
	}
	return true;
}

// 2 ^ 64 是上限，故 只能处理母串长度 <64 的情况;
int main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	int n; // 带输入的字符串个数;
	vector<string> vs; // 待输入的字符串;
	string s; // 临时存储输入的字符串;
	string s_little; // s输入的最短的字符串;
	while (cin >> n) {
		while (n--) {
			cin >> s;
			vs.push_back(s); // 存入字符串;
			if (s_little.length() < s.length()) {
				s_little = s;
			}
		}
		clock_t startTime = clock();
		// 确保遍历的是短字符串的所有子序列，并且是采用剔除元素的方式、自长到短遍历
		
		int len = s_little.length();
		int cont = 1 << len;
		string subSeq; // 临时存储子序列;
		set<string> ss; // 存储所有公共子序列;
		int longest = 0; // 最长公共子序列长度;
		bool flag = false; // 公共子序列是否存在;
		// i 将会直接影响到选择子集元素个数的多少（二进制表示）;
		for (int i = cont - 1; i >= 0; --i) {
			for (int j = 0; j < len; ++j) {
				if (i & (1 << j)) {
					//cout << s1[j];
					subSeq += s_little[j];
				}
			}
			//cout << "subSeq = " << subSeq << endl;
			// 接着判断 s_little 的子序列 subSeq 是否也同时是 其他字符串 的子序列;
			
			if (isComSeq(vs,subSeq)) {
				if (longest <= subSeq.size()) { // 是公共子序列不行，还得是最长公共子序列才进行存储;
					ss.insert(subSeq);
					longest = subSeq.size();
					flag = true; // 不放在 if 语句外边实为减少不必要的赋值次数;
				}
			}
			subSeq.clear(); // 记得重置为空;
			
		}
		// 不存在公共序列则输出空串;
		//if (ss.empty()) {// 此判别条件存在漏洞，因为两个任意字符串至少存在  空串 作为公共子序列，故需要立flag;
		if (!flag) {
			cout << endl;
		}
		else {
			for (auto item : ss) {
				/*cout << item << endl;*/ // 输出所有公共子序列;
				if (item.length() == longest) {
					cout << item << endl;
					//break; // 只需要输出ACSLL最小的最长公共子序列时，break;
				}
			}
		}
		// 重置容器为空;
		s_little.clear();
		vs.clear();
		// ss.clear(); // ss 是局部声明，清空没有必要; 
		// longgest = 0; 同理;
		cout << "总共耗时：" << double(clock() - startTime) / CLOCKS_PER_SEC << "s" << endl;
	}
	return 0;
}

测试样例：

鼠标置于此处可预览图片（Chrome）

拓展：N个字符环，求最长公共子序列？

代码实现：

#include <iostream>
#include <string>
#include <ctime>
#include <algorithm>
#include <set>
#include <vector>
#include <cassert>
using namespace std;

// 判断字符串subSeq中的每一个字符在字符串str中的出现顺序是否为递增
bool isSubsequence(const string& str, const string& subSeq) {
	int index = -1; //设为-1而不是0，因为后边还要 +1;
	for (char ch : subSeq) {
		index = str.find_first_of(ch, index + 1); // 起始位置得是下一位，故需要 +1;
		if (index == str.npos) {
			return false;
		}
	}
	return true;
}

// 字符串转字符环;
vector<string> stringToRing(const string& str) {
	vector<string> vs;
	for (int i = 1; i <= str.size(); ++i) {
		string str_right(&str[i], str.size() - i);
		// string s_right(str, i, str.size() - i); // 等效写法 1 ;
		// string s_right = str.substr(i, str.size() - i); // 等效写法 2 ;
		string str_left(str, 0, i);
		string s = str_right + str_left;
		// cout << s << endl;
		vs.push_back(s);
	}
	// 一个字符环 包含 n个与源字符串等长的字符串（n为源字符串的元素个数，即长度）;
	assert(vs.size() == str.length());
	return vs;
}

// 多个字符环的公共子序列判断;
bool isComSeq(const vector<string>& vs, const string& subseq) {
	
	for (string str : vs) {
		// 在当前字符环中是否存在该子序列，存在一次即可满足条件;
		bool flag = false; 
		for (string item : stringToRing(str)) {
			if (isSubsequence(item, subseq)) {
				flag = true; // 存在一次即可;
				break;
			}
		}
		// 当前环找不着该序列;
		if (!flag) {
			return false;
		}
	}
	return true;
}

// 2 ^ 64 是上限，故 只能处理母串长度 <64 的情况;
int main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	int n; // 带输入的字符串个数;
	vector<string> vs; // 待输入的字符串（源字符串）;
	string s; // 临时存储输入的字符串;
	string s_little; // s输入的最短的字符串;
	while (cin >> n) {
		while (n--) {
			cin >> s;
			vs.push_back(s);  // 存入字符环;
			if (s_little.length() < s.length()) {
				s_little = s;
			}
		}
		clock_t startTime = clock();

		string subSeq; // 临时存储子序列;
		set<string> ss; // 存储所有公共子序列;
		int longest = 0; // 最长公共子序列长度;
		bool flag = false; // 公共子序列是否存在;

		for (string item : stringToRing(s_little)) {

			// 确保遍历的是短字符串的所有子序列，并且是采用剔除元素的方式、自长到短遍历
			int len = item.length();
			int cont = 1 << len;

			// i 将会直接影响到选择子集元素个数的多少（二进制表示）;
			for (int i = cont - 1; i >= 0; --i) {
				for (int j = 0; j < len; ++j) {
					if (i & (1 << j)) {
						//cout << s1[j];
						subSeq += item[j];
					}
				}
				//cout << "subSeq = " << subSeq << endl;
				// 接着判断 s_little 的子序列 subSeq 是否也同时是 其他字符串 的子序列;

				if (isComSeq(vs, subSeq)) {
					if (longest <= subSeq.size()) { // 是公共子序列不行，还得是最长公共子序列才进行存储;
						ss.insert(subSeq);
						longest = subSeq.size();
						flag = true; // 不放在 if 语句外边实为减少不必要的赋值次数;
					}
				}
				subSeq.clear(); // 记得重置为空;

			}
		}
		// 不存在公共序列则输出空串;
		//if (ss.empty()) {// 此判别条件存在漏洞，因为两个任意字符串至少存在  空串 作为公共子序列，故需要立flag;
		if (!flag) {
			cout << endl;
		}
		else {
			for (auto item : ss) {
				/*cout << item << endl;*/ // 输出所有公共子序列;
				if (item.length() == longest) {
					cout << item << endl;
					//break; // 只需要输出ACSLL最小的最长公共子序列时，break;
				}
			}
		}
		// 重置容器为空;
		s_little.clear();
		vs.clear();
		ss.clear(); // ss 是局部声明，清空没有必要; 
		longest = 0; // 同理;
		cout << "总共耗时：" << double(clock() - startTime) / CLOCKS_PER_SEC << "s" << endl;
	}
	return 0;
}

测试样例：

鼠标置于此处预览（Chrome）

题目补充：

题目来源：

ACM-ICPC 2018 北京赛区网络预赛 Tomb Raider

特别说明：

该考题的输出仅仅是一个ACSLL码最小的最长公共子序列串，
自己的测试是左右公共子序列。

有上述 从N个字符串找最长公共子序列，到N个字符环找最长公共子序列的过程可以发现：环的公共子序列的结果数量明细增多。

并且值得注意的是：
代码证容易被遗漏的地方是， s_little也需要先生成对应的字符环（多个字符串），再各自去生成各自的所有子序列，然后拿来校验。
而不是仅仅针对 s_little 的源字符串生成所有子序列。

其他说明：

博客补充以强化理解：

助你深刻理解——最长公共子串、最长公共子序列（应该是全网数一数二的比较全面的总结了）

转载请注明出处:

https://blog.csdn.net/I_love_you_dandan/article/details/103227017

以上代码皆为本人亲自码字、亲自测试，如有问题需要咨询或者指正，可以直接在评论区留言或者发送私信进行友好交流。

联系方式：2636105163@qq.com
2019/11/24  20:43

题目

求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4
输入描述:
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000
输出描述:
输出字符串的最长递增子序列的长度
样例输入:
复制
3
aaa
ababc
abklmncdefg
样例输出:
1
3
7

分析：

求字符串的最长递增子序列，可将问题分解为一个个小问题，先计算字符串长度为1的最长递增，再计算长度为2，以此类推，直到计算为n

思路：（1.以下j表示数组下标 2.括号中为举例说明 如：dabdbf）

1. 计算长度为前j个字符串子串的最长递增子序列（如：babd）
2. 将第j个字符与前j-1个字符一一比较（如，d与bab进行比较）
3. 若第j个大于前j-1个中任意一个字符k，取dp[j]与dp[k]+1最大值
4. dp[k]+1是因为前k个字符的最大递增序列加上第j个字符，最大递增子序列为dp[k]+1

代码如下：

/*
求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4
输入描述:
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000
输出描述:
输出字符串的最长递增子序列的长度
样例输入:
复制
3
aaa
ababc
abklmncdefg
样例输出:
1
3
7
*/
#include<stdio.h>
#include<string.h>
int main(void){
	int n;
	int i,j,k;
	scanf("%d",&n);
	char array[n][10000]; //存储字符数组
	int flag[n]; 
	for(i=0;i<n;i++){
		scanf("%s",&array[i]);
	}
	//计算递增序列 
	for(i=0;i<n;i++){
		int length = strlen(array[i]);
		int dp[length]; //利用动态规划计算每一步的最长子序列 
		for(j=0;j<length;j++){
			dp[j]=1;
		}
		for(j=0;j<length;j++){
			for(k=0;k<j;k++){
				if(array[i][j] > array[i][k]){  //如果str[k] < str[j] 取最大值 
					dp[j]=max(dp[k]+1,dp[j]); 
				}
			}
		}
		flag[i]=dp[length-1]; 
	} 
	
	for(i=0;i<n;i++){
		printf("%d\n",flag[i]);
	}
	return 0;
}

/*
	比较num1和num2的最大值 并返回最大值 
*/
int max(int num1,int num2){
	if(num1>num2){
		return num1;
	}else if(num1<num2){
		return num2;
	}else{//等于 
		return num1;
	}
}