题意:
求 n 个串里的 LCS, 长度相同时按照字典序排序
solution:
断环为链, 二进制枚举子序列, 压入 vector, 按照字典序排序
把出现次数为 n 的, 压入第二个 vector
输出最长的第二个 vector 里最长的序列
- #include<bits/stdc++.h>
- #define endl '\n'
- using namespace std;
- bool cmp(string a,string b)
- {
- return a.size()<b.size();
- }
- int main() {
- // iOS::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- int n;
- while(cin>> n) {
- string s;
- vector<string>a;
- if(n == 1) {
- cin>> s;
- int sz= s.size();
- vector<string>xx;
- s+=s;
- // cout <<s << endl;
- for(int i = 0; i < sz;i++) xx.push_back(s.substr(i,sz));// 截取起点为 i 长度为 sz 的字串
- sort(xx.begin(),xx.end());
- for(int i = 0; i < xx.size(); i++) cout <<xx[i]<<endl;
- cout << xx[0] << endl;continue;
- }
- for(int i = 0; i < n; i++) {
- cin>> s;
- int sz = s.size();
- s += s;
- vector<string>b;
- for(int j = 0; j <sz; j++){// 断环为链
- for(int k = 1; k < (1 << sz); k++) {// 用枚举子集来表示序列
- string t;
- for(int p = 0; p < sz; p++) {
- if(k & (1 << p)) {
- t += s[j + p];
- }
- }
- //cout << t << endl;
- b.push_back(t);
- }
- //cout << endl;
- }
- sort(b.begin(),b.end());
- b.erase(unique(b.begin(),b.end()),b.end());// 每一个串的子序列按照字典序排序并去重
- for(int j = 0; j < b.size(); j++) {// 把每一个串的子序列加入总的字符串里
- a.push_back(b[j]);
- }
- }
- sort(a.begin(),a.end());// 按照所有串的子序列
- // for(int i = 0; i < a.size(); i++) cout << a[i] <<endl;
- int ct = 1, maxx = 0;
- vector<string>c,d;
- for(int i = 1; i < a.size(); i++) {
- if(a[i] == a[i- 1]) ct++;
- else ct = 1;
- if(ct == n) c.push_back(a[i]),maxx=max(maxx,(int)a[i].size());//n 个串里的公共子序列
- }
- // for(int i = 0; i < c.size(); i++) cout << c[i] <<endl;
- if(c.size() == 0) {
- cout << 0 << endl; continue;
- }
- for(int i = 0 ; i < c.size(); i++) {
- if(c[i].size() == maxx){
- cout<<c[i]<<endl;break;
- }
- }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2778066.html