解いた問題

7/01/2011

AOJ1215

尺取

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

int main(void)
{
  while(true){
    string s, t;
    for(string u; getline(cin, u) && u.size(); t += u);
    getline( cin, s );

    if( s.size() && t.size() ); else break;

    map<char, int> cnt;
    int occ = 0;

    map<char, int> demand;
    for(int i=0; i<s.size(); ++i){
      ++demand[s[i]];
    }
    const int OCC = demand.size();

    vector<string> v;
    int i, j;
    i = j = 0;

    while( j < t.size() ){
      while( i < t.size() && occ < OCC ){
        char c = t[i++];
        if( demand[c] && demand[c] == ++cnt[c] )++occ;
      }
      if( occ != OCC )break;
      while(j < i){
        char c = t[j];
        if( demand[c] && demand[c] == cnt[c] )break;
        --cnt[c];
        ++j;
      }
      if(j == i)break;
      v.push_back( t.substr( j, i - j) );
      --cnt[ t[j++] ];
      --occ;
    }

    int mn = (1 << 24);
    for(int i=0; i<v.size(); ++i){
      mn = min( mn, (int)v[i].size() );
    }

    string u;
    int same_len = 0;
    for(int i=0; i<v.size(); ++i){
      if( v[i].size() == mn ){
        if( u.size() == 0 )u = v[i];
        ++same_len;
      }
    }

    cout << same_len << endl;
    if( same_len )cout << endl;
    for(int i=0; i<u.size(); ++i){
      cout << u[i];
      if( (i+1) % 72 == 0 )cout << endl;
    }
    if( u.size() && u.size() != 72 )cout << endl;
    cout << endl;
    
    getline( cin, s );
  }
  return 0;
}

0 件のコメント :

コメントを投稿