読者です 読者をやめる 読者になる 読者になる

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;
}