题目链接

题意

给n个字符串，每个字符串是一个环（就是说起点任意），求n个字符串的最长公共子序列（LCS)

解题思路

比赛的时候刚看到这个题目要求n个字符串的lcs，并且没个字符串可以起点不一样，就是说字符串s都有s.length个不同的排列，求所有n个s里s.length个lcs，时限只有1s，求两个字符串的lcs有n^2的复杂度，思路肯定不是这样，而且n和s.length很小，发现可以直接暴力求每个字符串的所有子串（相当于求集合的所有子集）,然后用set保存，答案就是n个set里最长的公共串。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
string S[12];
set<string> cset[12];

void getstr(string a,int mark,int length,int k)
{
	bool allZero=true;
	int limit=1<<length;
    string s;
	for(int i=0;i<length;++i)
	{
		if(((1<<i)&mark)!=0)
		{
			allZero=false;
            s += a[i];
		}
	}
    if(s!=""||s.size()>1)
        cset[k].insert(s);
}

void subset(string a,int length,int k)
{
	if(length>31) return;
	int lowFlag=0;
	int highFlag=(1<<length)-1;	
	for(int i=lowFlag;i<=highFlag;++i)
	{
		getstr(a,i,length,k);
	}
}

int main()
{
    int n = 0;
    while(cin >> n){
        for(int i=0;i<n;i++){
            cset[i].clear();
            cin >> S[i];
            int len = S[i].size();
            S[i] += S[i];
            for(int j=0;j<len;j++){
                string s(S[i].begin()+j,S[i].begin()+len+j);
                subset(s,s.size(),i);
            }
        }
        vector<string> ans;
        for(string s:cset[0]){
            bool ok = 1;
            for(int i=1;i<n;i++){
                if(cset[i].count(s)==0){
                    ok = 0;
                    break;
                }
            }
            if(ok) ans.push_back(s);
        }
        if(ans.size()==0){
            cout << "0" << endl;
            continue;
        }
        sort(ans.begin(),ans.end());
        string res;
        int len = 0;
        for(string s:ans){
            if(s.size()>len){
                len = s.size();
                res = s;
            }
        }
        cout << res << endl;
    }
    return 0;
}