TopCoder SRM 702 Div1 Medium RepeatedStrings

気づけば簡単だけど本番に気づける気がしない。
https://community.topcoder.com/stat?c=problem_statement&pm=14264

問題

良い文字列とは以下のものを指す。

• "()"は良い文字列である。
• 良い文字列Sがあったとき、それを1回以上繰り返して全体を括弧で囲んだもの"(SS...SS)"もよい文字列である。
  • これは一般的なcorrect bracket sequenceの定義と異なる点に注意。
• それ以外はよい文字列ではない。

文字列sが与えられる。
sの部分文字列として得られる良い文字列のうち、辞書順k番目のものを求めよ。
(部分文字列を取り出した結果同じ文字列が複数回登場しても1個とカウントする)

解法

s	≦150なので、実際に150文字以下の部分文字列を全部列挙してしまおう。

そうするとたった163777個しかない。
あとは163777個をソートし、sの部分文字列となるもののうちk個目を答えればよい。

class RepeatedStrings {
	public:
	int issubstr(string a,string b) {
		int x=0;
		FORR(c,b) if(c==a[x] && ++x>=a.size()) return 1;
		return x>=a.size();
	}
	string findKth(string s, int k) {
		vector<string> S;
		S.push_back("()");
		int i,j;
		FOR(i,S.size()) {
			string t=S[i];
			while(t.size()<=s.size()) {
				S.push_back("("+t+")");
				t+=S[i];
			}
		}
		sort(ALL(S));
		S.erase(unique(ALL(S)),S.end());
		FORR(r,S) if(issubstr(r,s)) {
			if(k--==1) return r;
		}
		return "";
		
		
	}
}

まとめ

Div2 Hardならともかく、Div1 Mediumで全列挙で済む問題、逆に盲点で気づきにくそう。