USACO 3.1 Contact

The problem can be reduced to a string search and counting problem. The search space is any possible sub strings with size between A and B inclusive. Use a map to record the frequency of the occurrence of each bit pattern (string). Nothing dramatic, but the output formatting is quite nuisance. 输出坑爹!

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <map>
#include <unordered_map>
#include <climits>
#include <sstream>

using namespace std;

int A, B, N;
int main() {
  ifstream fin("contact.in");
  ofstream fout("contact.out");
  fin >> A >> B >> N;
  string s, t;
  while (fin >> t) {
    s += t;
  }
  cout << s << endl;
  
  map<string, int, std::greater<string>> map;
  const int size = (int)s.size();
  for (int i = 0; i < size; ++i) {
    for (int j = A; j <= B && i + j <= size; ++j) {
      string sub = s.substr(i, j);
      map[sub]++;
    }
  }
  std::vector<pair<int, string>> v;
  unordered_map<int, int> cm; // Key: frequence; Val: frequence count.
  for (auto iter = map.begin(); iter != map.end(); ++iter) {
    v.emplace_back(make_pair(iter->second, iter->first));
    cm[iter->second]++;
  }
  sort(v.begin(), v.end(), [] (const pair<int, string> &a,
                               const pair<int, string> &b) {
    if (a.first > b.first) return true;
    if (a.first < b.first) return false;
    int sa = (int)a.second.size(), sb = (int)b.second.size();
    if (sa < sb) return true;
    if (sa > sb) return false;
    return a.second < b.second;
  });
  
  for (int i = 0, count = 0; count < N && i < v.size();) {
    int cnt = cm[v[i].first];
    fout << v[i].first << endl;
    if (cnt > 1) {
      for (int j = 0; j < cnt; ++j) {
        if ((j + 1) % 6 == 0 || j == cnt - 1) {
          fout << v[i + j].second << endl;
        } else {
          fout << v[i + j].second << " ";
        }
      }
      i += cnt;
    } else {
      fout << v[i].second << endl;
      ++i;
    }
    ++count;
  }
}