kmjp's blog

競技プログラミング参加記です

Saiko~ No Contesuto #01 : 焼肉チャレンジャーズ

このタイトルは何ネタだろう?
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;
		}
	}
	
}

まとめ

どんな事情だろう。