このタイトルは何ネタだろう?
https://www.hackerrank.com/contests/camypapercon01/challenges/enumerate-lcs
問題
2つの文字列S,Tが与えられる。
LCS(S,T)に該当する文字列を列挙せよ。
解法
S,Tの長さが短いので、Sの部分文字列を2^|S|個列挙し、それぞれがTに含まれるか判定していく。
条件を満たす部分文字列のうち、最長のものを出力すればよい。
set<string> R[17]; string S,T; bool inc(string sub,string full) { int cur=0; FORR(r,full) if(cur<sub.size() && sub[cur]==r) cur++; return cur==sub.size(); } void solve() { int i,j,k,l,r,x,y; string s; cin>>S>>T; for(int mask=0;mask<1<<S.size();mask++) { s=""; FOR(i,S.size()) if(mask&(1<<i)) s+=S[i]; if(inc(s,T)) R[s.size()].insert(s); } for(i=16;i>=0;i--) { if(R[i].size()) { cout<<R[i].size()<<endl; FORR(r,R[i]) cout<<r<<endl; break; } } }
まとめ
どんな事情だろう。