UVa11860 Document Analyzer
問題文
http://uva.onlinejudge.org/external/118/11860.html
概要
アルファベットの小文字と記号で表された文書がある。一つの単語はアルファベットの小文字以外の文字で区切られる。全ての単語を含む区間を出力せよ。
解法
尺取り法で解く。
#define INF (1<<29) #define allof(x) (x).begin(), (x).end() vector<string> document; vector<string> wordlist; void input() { document.clear(); string word; char ch; while(1) { scanf("%c", &ch); if(isalpha(ch)) { word += ch; if(word == "END") { break; } } else { if(word.empty()) {} else { document.push_back(word); word.clear(); } } } wordlist = document; sort(allof(wordlist)); wordlist.erase(unique(allof(wordlist)), wordlist.end()); } pair<int, int> solve() { input(); pair<int, int> ret(0, INF); map<string, int> mp; int L = 0, partial_kinds = 0; for(int R=0; R<(int)document.size(); R++) { if(mp[document[R]] == 0) { partial_kinds ++; } mp[document[R]] ++; for(; mp[document[L]]>1; mp[document[L]]--, L++); if(partial_kinds == (int)wordlist.size()) { if(ret.second - ret.first > R-L) { ret.first = L, ret.second = R; } } } ret.first ++, ret.second ++; return ret; } int main() { int Tc; cin >> Tc; for(int tcnt=1; tcnt <= Tc; tcnt++) { pair<int, int> ans = solve(); cout << "Document " << tcnt << ": " << ans.first << ' ' << ans.second << endl; } return 0; }