PIPI1084 最长公共子序列Ⅱ（暴力+set+状压）

题目描述

PIPI又来刁难胖虎了~

现在PIPI有n个字符串项链，它要你求出这n个环的最长公共子序列，并输出~

PS：注意每个字符串都成环了，首尾相连~

输入

多组数据

第一行为一个整数n，1<=n<=10

接下来n行，每行一个字符串，保证字符串长度不超过8.

输出

输出一个字符串，代表n个串的最长公共子序列。若不存在，输出0.若有多个答案，输出字典序最小的。

样例输入

2 abcdefg zaxcdkgb 5 abcdef kedajceu adbac abcdef abcdafc 2 abc def

样例输出

acdg acd 0

数据量很小，考虑每个字符串把所有可能的子串都保存在set中 set有个count()函数，可以返回集合中是否含有某个key 用状态压缩把字符串的可能子串表示出来

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
set<string> st[N];
set<string>::iterator it;
string s, ans;
int n;
int main() {
	while (cin >> n) {
		for (int i = 1; i <= n; i++) {
			st[i].clear();
		}
		ans = "";
		for (int i = 1; i <= n; i++) {
			cin >> s;
			int len = s.size();
			for (int l = 1; l < 1<<len; l++) {
				string tmp = "";
				for (int j = 0; j < len; j++) {
					if (l & 1 << j) tmp += s[j];
				}
				st[i].insert(tmp);
				int nt = tmp.size();
				for (int j = 1; j < nt; j++) {
					string sub = tmp.substr(j, nt - j) + tmp.substr(0, j);
					st[i].insert(sub);
				}
			}
		}
		for (it = st[1].begin(); it != st[1].end(); it++) {
			s = *it;
			bool flag = true;
			for (int i = 2; i <= n; i++) {
				if (!st[i].count(s)) {
					flag = false;
					break;
				}
			}
			if (!flag) continue;
			if (s.size() > ans.size()) {
				ans = s;
			} else if (s.size() == ans.size() && ans > s) {
				ans = s;
			}
		}
		if (!ans.size()) {
			printf("0
");
		} else cout << ans << endl;
	}
	return 0;
}