Problem 1215 : Co-occurrence Search
Problem H: Co-occurrence Search
問題概要
与えられた文字の集合を含む最短の文字列を文章から探して答えよ。
複数ある場合数を数えて、最初に見つかったものを出力せよ。
解法
与えられた文字の集合をmapにいれて、文章を最初から見ていって、
mapにその文字が最後に現れた場所を記録して、
現在の場所との差異をみて長さをだした。
ソース
#include<iostream> #include<string> #include<algorithm> #include<map> #define REP(i,b,n) for(int i=b;i<(int)n;i++) #define rep(i,n) REP(i,0,n) #define FOR(it,o) for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it) using namespace std; const int INF = 1000000000; typedef long long lli; int main(){ string s; while(getline(cin, s)){ string S, key; S += s; while(getline(cin, s)){ if(s.length() == 0)break; S += s; } if(S.length() == 0)break; while(getline(cin, s)){ if(s.length() == 0)break; key += s; } map<char, int> M; FOR(it, key){ M[*it] = -1; } int miniLen = INF, cnt = 0; string ans; rep(i, S.length()){ if(M.find(S[i]) == M.end())continue; M[S[i]] = i; bool valid = true; int left = INF; FOR(it, M){ if(it->second < 0){ valid = false; break; } left = min(left, it->second); } if(!valid)continue; if(i - left == miniLen){ cnt++; } else if(i - left < miniLen){ miniLen = i - left; cnt = 1; ans = S.substr(left, i-left+1); } } cout << cnt << endl; if(cnt == 0){ cout << endl; continue; } cout << endl; int now = 0; while(now < (int)ans.length()){ cout << ans.substr(now, min(72, (int)ans.length() - now)) << endl; now += 72; } cout << endl; } return 0; }